Comparing pivot choosing methods in quicksort

I have seen various tweaks for quicksort and to establish their usefulness, I designed a program that randomly generates arrays and times how long quicksort takes to sort them. Right now I'm focusing on how the pivot is chosen. I'm comparing choosing the first element as the pivot versus choosing the median of first, middle and last elements. I came across an implementation that presorts the first, middle and last element and have to implemented it for my tests.

Here is the original code I got the idea from:

public static int medianOf3(int[] intArray, int left, int right) {
    int center = (left + right) / 2;

    if (intArray[left] > intArray[center])
      swap(intArray, left, center);

    if (intArray[left] > intArray[right])
      swap(intArray, left, right);

    if (intArray[center] > intArray[right])
      swap(intArray, center, right);

    swap(intArray, center, right - 1);
    return intArray[right - 1];
}

First of all, I want to make sure I understand it.

• The index of the middle element is computed

• The 3 if statements rearange the first, middle and last element so they are in order relative to only each other (so for example 5,1,4,9,8 => 4,1,5,9,8). I am interested in the math behind how it is known that only 3 if statements are needed, since there are 3! (=6) permutations of 3 elements.

• The median is swapped so it's beside the largest valued element of the 3. Latter in the code I noticed partitionIt() has int rightPtr = right - 1; and I think the -1 is to avoid one extra iteration of the while loop as it's known [right-1] and [right] is a sorted sub array of size 2. Is this right? I don't really see how this benefits the algorithm as quicksort works on the principle of finding the final location of a pivot, and doesn't care a bout a sorted subarray.

```
/*returns index of element with median value of beginning, middle and end elements
sorts beginning, middle and end element relative to each other*/
private static int medianOf3(

Consistency of results

When you compile a Java program, you don't actually do much in the way of performance optimization of the code. Some basic things are done, but the real optimization is done by the JIT compiler at Java runtime.

The JIT compiler is able to take your class methods and analyze them, using statistics it gathers during your method rin,a n other items, to make your code really efficient. It can them mke bbigger decisions about performance as well. JIT is the performance king.

The JIT process takes time though, and the cost of the compile for code that runs once, or just a few times, is seldom worth it. So, JIT does nothing until the code has run many times (hundreds). Then, even if the code has been JIT compiled once, it may be determined that the code would benefit from a second, and even third compile with different characteristics.

It is only when you get to this final stage that it starts to make sense to performance-time/benchmark the code. The JIT based code can be thousands of times faster than the uncompiled code.

Consider this code here: https://softwareengineering.stackexchange.com/a/246535/109836

The first 1000 loops ran at an average of > 7ms.... average.

The second 1000 loops ran at an average of 1.6ms

The 101st 1000 loops ran at an average of 1.2ms.

The code was well-compiled by then.

When benchmarking Java, you have to 'warm up' the code so that you are not running in to compile times, or poorly compiled code when you do your performance work. warming up normally requires running the sensitive code thousands of times (one of the best optimizations available is inlining method calls, and that requires the calling method to be run a lot, not just the actual code doing the work).
The median of three

The median of three logic is relatively simple, though it can be confusing.

If you have three values, A, B, and C. What are the possible combinations?

A B C
A C B
B A C
B C A
C A B
C B A

Now, if A is less than B, and B is less than C, let's follow the logic through:

if(arr[beginning] > arr[middle])
    swap(arr, beginning, middle);

Is the first bigger than the second value. This is possible with the following combinations (marked with an asterist *):

A B C
A C B
B A C *
B C A
C A B *
C B A *

So, half the combinations could be like this. If it is, then swap the first two:

A B C
A C B
A B C *
B C A
A C B *
B C A *

OK, so, now for the second test:

if(arr[beginning] > arr[end])
    swap(arr, beginning, end);

I'll mark the instances where this is possible with a hash mark #

A B C
A C B
A B C *
B C A   #
A C B *
B C A * #

Swap them if they are:

A B C
A C B
A B C *
A C B   #
A C B *
A C B * #

Final test is:

if(arr[middle] > arr[end])
    swap(arr, middle, end);

A B C
A C B     @
A B C *
A C B   # @
A C B *   @
A C B * # @

Swap them:

A B C
A B C     @
A B C *
A B C   # @
A B C *   @
A B C * # @

StackExchange Code Review Q#56481, answer score: 6