Quicksort with Insertion Sort and Improved Pivot Selection

Here's a Quicksort I had fun writing and improving, so I thought I'd post it here. In my (brief) testing it's about 15% to 20% faster than Java's Arrays.sort().

The sort routine is a fairly vanilla Quicksort. The main improvements are to the pivot selection, and the Quicksort switches to an Insertion Sort for small sub arrays.

The pivot selection is pretty basic. Mostly I just use more data points than "middle of three." Actually I call a "middle of three" algorithm three times, then I just take the middle of those points as a decent pivot. More samples means more chances of getting a good pivot for Quicksort, which helps it immensely.

The other interesting idea in the pivot selection is which nine points to consider when taking the middle of three. I compute an offset to spread the points around more. Most data comes from an already sorted source. So sampling three points adjacent to each other might not actually sample random points. So I spread the offset throughout the array to try to obtain a better selection of input points.

package SimpleUtils.sort;

import java.util.Comparator;

/**  Sort utilities.
*
* @author Brenden Towey
*/
public class Sort
{

/**
* Sorts an array of Comparable.  Null values are moved to the end of the
* array by this routine, so arrays containing null values can be safely
* sorted.
*
* @param <T> Any Comparable.
* @param table The array to be sorted.
* @return The number of non-null elements in the array.
*/
public static <T extends Comparable<? super T>> int sort( T[] table )
{
int newLength = moveNullsToEnd( table );
quickSort( table, Comparator.naturalOrder(), 0, newLength - 1 );
return newLength;
}

/**
* Moves null values to the end of an array.  This is done in
* preparation for sorting to remove nulls from the array.  The
* idea of moving nulls to the end of an array is synonymous with compacting
* the array by moving all non-null elements to the beginning.
*
* <p>This method returns the number of non-null elements in the array.
* The index of the last non-null element will be the one less than the
* return value.
*
* @param table Table to move nulls to end.
* @return The number of non-null elements.
*/
public static int moveNullsToEnd( Object[] table )
{
int end = table.length-1;
for( int i = 0 ;; ) {
while( i < table.length && table[i] != null ) i++;
if( i == table.length ) break;
while( table[end] == null ) end--;
if( i < end ) {
table[i] = table[end];
table[end] = null;
} else
break;
}
return end+1;
}

/**
* A quicksort implementation for arrays.  Null values are not checked by
* this method.  Therefore a "null safe" Comparator must be used, such
* as {@code Comparator.nullsFirst()}, or the array range to be sorted
* must be free of nulls.
*
* @param <T> Any type.
* @param comp A Comparator for T.
* @param table An array of T to sort.
* @param first First element in the (sub) array to sort, inclusive.
* @param last Last element in the (sub) array to sort, inclusive.
*/
public static <T> void quickSort( T[] table, Comparator<T> comp, int first,
int last )
{
//  System.out.println( "first="+first+", last="+last+" table="+Arrays.deepToString( table ) );

// The value of INSERT is empirically determined.  Basically smaller values
// are assumed to be better, up to a point, then they get worse.
// In testing, sort times are quite close, differing only by few
// tens of milliseconds over one million elements.
// 10 is used here as it "theorectically" should be good all other
// things being equal, and its times were generally smaller than other
// numbers, although only slightly.

final int INSERT = 10;

if( last - first < INSERT )
insertionSort( table, comp, first, last );
else {
int pivot = partition( table, comp, first, last );
quickSort( table, comp, first, pivot - 1 );
quickSort( table, comp, pivot + 1, last );
}
}

/**
* A stable insertion sort.  This routine does not check for nulls before
* sorting.  Therefore a "null-safe" comparator must be used, such as
* {@code Comparator.nullsLast()}, or the array range must be free of
* null values.
*
* @param <T> Any type.
* @param table An array to be sorted.
* @param comp A Comparator to use.
* @param first The first element to sort, inclusive.
* @param last The last element to sort, inclusive.
*
* @throws ArrayIndexOutOfBoundsException if either first or last are beyond the
* bounds of the array table.
* @throws NullPointerException if the array contains nulls and a "null-safe"
* Comparator is not used.
*
* @throws NullPointerException if table or any element is null.
*/
public static <T> void insertionSort( T[] table, Comparator<T> comp,
int first, int last )
{
for( int i = first+1; i < last+1; i++ ) {
T temp = table[i];
int j = i-1;
for( ; (j >= 0) && comp.compare( table[j], temp ) > 0; j-- ) {
table[j+1] = table[j];
}
table[j+1] = temp;
}
}

/**
* Partition for quicksort.
*
* @param <T> Any type.
* @param table An array to sort.
* @param comp Comparator to use.
* @param first Index of first element to sort, inclusive.
* @param last Index of last element to sort, inclusive.
* @return
*/
private static <T> int partition( T[] table, Comparator<T> comp, final int first,
final int last )
{
int pivotIndex =  getPivotIndex( table, comp, first, last );
T pivot = table[ pivotIndex ];
swap( table, first, pivotIndex );

int lower = first+1;
int upper = last;
do {
while( (lower < upper) && comp.compare( pivot, table[lower] ) >= 0 )
lower++;
while( comp.compare( pivot, table[upper] ) < 0 )
upper--;
if( lower < upper )
swap( table, lower, upper );
} while( lower < upper );
swap( table, first, upper );
return upper;
}

/**
* Finds a pivot index by comparing up to nine values, to
* determine the middle of those nine.
*
* @param <T> This works out to "anything that is Comparable"
* @param table Array of Comparable.
* @param first index of array to start looking for pivot.
* @param last index of array of last value to consider for pivot.
* @return The index of the pivot to use.s
*/
private static <T> int getPivotIndex( T[] table, Comparator<T> comp,
int first, int last )
{
int middle = (last+first) >>> 1;  // divide by 2

// if less than 9 total just return the middle one
if( last - first < 9 ) return middle;

// compute an offset to create a wider range of values
int offset = (last-first) >>> 3;  // divide by 8

// if 9 or more then we have nine values we can consider
int mid1 = mid( table, comp, first, first + offset, first + offset * 2 );
int mid2 = mid( table, comp, middle - offset, middle, middle + offset );
int mid3 = mid( table, comp, last, last - offset, last - offset * 2 );
return mid( table, comp, mid1, mid2, mid3 );
}

/**
* Find the middle value out of three, for an array of Comparable.
*
* @param <T> Any type with a Comparator.
* @param table A table of type T.
* @param comp A Comparator for type T.
* @param first index of first element to compare.
* @param second index of second element to compare.
* @param third index of third element to compare.
* @return index of middle element.
*/
// package private for testing
static <T> int mid( T[] table, Comparator<T> comp, int first, int second, int third )
{
T firstv = table[first];
T secondv = table[second];
T thirdv = table[third];

// return (a > b) ^ (a > c) ? a : (a > b) ^ (b > c) ? c : b;
boolean aGTb = comp.compare( firstv, secondv ) > 0;
boolean aGTc = comp.compare( firstv, thirdv ) > 0;
boolean bGTc = comp.compare( secondv, thirdv ) > 0;

return (aGTb ^ aGTc) ? first : (aGTb ^ bGTc) ? third : second;
}

/**
* Swaps two references in an array.
*
* @param table Array to swap elements.
* @param s1 index of first element to swap.
* @param s2 index of second element to swap.
*
* @throws IndexOutOfBoundsException if either index is outside of the
* bounds of the array.
*/
public static void swap( Object[] table, int s1, int s2 ) {
Object temp = table[s1];
table[s1] = table[s2];
table[s2] = temp;
}
}


Edit: I wanted to update this with new performance measurements. Regarding a suggestion:

Postpone insertion sort until the recursive phase completes. The array now is "almost" sorted; each element is within k steps from its final destination. Insertion sorting the entire array is still O(Nk) (each element takes at most k swaps), but it is done in a single function invocation

I tested this and got no improvement. In fact sort speed reduced considerably. As is, the quicksort above gives around 15% to 20% improvement over the built-in Arrays.sort(). By eliminating the call to the insertion sort and only calling it once at the very end of all partitions, speed improvement goes down to 7% to 0% or even a little less. So this turns out to be a mis-optimisation.

What I think is going on is that the temporal locality of reference provided by various CPU hardware caches is providing non-linear preformance. Even though we did eliminate 100,000 method calls, those method calls were previously made with "fresh data" still in the cache. When the insertion sort is delayed until the very end of all partitioning, some of that data has gone "stale" and is no longer in the cache. It has to be re-fetched from main memory.

I think it was Knuth who said to always test performance, and I think we've re-proven his admonishment here. Even though the optimization sounded good on paper, hardware provided non-linear performance which invalidated our simple intuitive analysis.

• You may want to eliminate the tail call to quickSort (Java itself does not optimize tail recursion).

Along the same line, it is beneficial to recur into a smaller partition, while looping over the larger one.

• Insertion sort implementation is suboptimal. The inner loop tests two conditions at each iteration. If you split the loop into two, depending on how temp compares to table[0], each one needs to test only one condition. In pseudocode,

    temp = table[i]
if temp < table[0]
// table[i] will land at index 0. Don't bother testing values.
for (j = i; j > 0; --j)
table[j] = table[j-1];
else
// table[0] is a natural sentinel. Don't bother testing indices.
for (j = i; table[j - 1] > temp; --j)
table[j] = table[j-1];
table[j] = temp;

• Your setup allows one more quite subtle optimization. The insertion sorts are working on the $$\\frac{N}{k}\$$ arrays of $$\k\$$ elements, resulting in $$\O(Nk)\$$ time complexity. Postpone insertion sort until the recursive phase completes. The array now is "almost" sorted; each element is within $$\k\$$ steps from its final destination. Insertion sorting the entire array is still $$\O(Nk)\$$ (each element takes at most $$\k\$$ swaps), but it is done in a single function invocation, rather than $$\\frac{N}{k}\$$ invocations your code makes.

If you are sorting a million-strong array, this spares you 100000 function invocations.

Besides, after the first $$\k\$$ rounds, the minimal element is placed correctly, and you may fall into the unguarded branch unconditionally.

• I don't see how last - first < 9 may ever be true. The code never calls partition (and consequently getPivotIndex()) for the ranges that small. Since it is a private method, nobody else would call it either.

• Thanks for the review! Regarding last - first < 9, it's there because I was experimenting with different values for INSERT. I can change INSERT to any value from 0 on up and the code still works. So last - first < 9 just catches the condition where someone has changed the value of INSERT. Aug 20, 2019 at 14:06
• Now you've got me looking at the insertion sort and I think j >= 0 is a mistake. I should be comparing vs first, not 0. The code I wrote could advance j to values less than first. Aug 20, 2019 at 14:52
• Postpone insertion sort until the recursive phase completes. Wow, that is a pretty cool optimization. I think I might have to actually test that out and see if there's speed improvements in the stress tester. Thanks for that! Aug 22, 2019 at 16:29
• I tested your suggestion to move the insertion sort to the end of the quicksort implementation, only calling it once instead of once per end of partition. The result was a slower sort time. I think that cache is providing non-linear performance, and delaying the insertion sort turns out to not be an optimization, unfortunately. See my updated question for a bit more info. Aug 28, 2019 at 15:02

Formatting

In idiomatic java,

• curly braces go on the same line, not a newline
• optional curly braces are always used. This provides consistency and reduces the risk of forgetting to add them when refactoring.
• there is no whitespace after an ( or before a )
• there is whitespace after control flow keywords (for, while, etc)
• ALL_CAPS are used only for constant member variables

It would be preferable to use finalwhere possible to clarify intent and improve readability.

All your methods refer to a T[] as a "table", but arrays are not the same thing as tables.

Don't use random abbreviations. Is a comp a comparison or a Comparator? I don't want to have to guess. Variables should clearly indicate what they hold. Something like aGTb is gibberish. Use a descriptive name.

Design

It's unclear to me that there's value in offering sort, given the existence of Arrays.sort.

If you're trying to write a generally useful sorting class that provides some advantage over what already exists in the API, not supporting Lists also seems like a major oversight.

All your public methods throw a NullPointerException when the array or comparator parameters are null, and that's not documented anywhere. Either write a permissive library that can sort a null array (just return it), or document that you're going to fail-fast on null inputs. Failing fast on a null comparator is probably correct, but should be documented.

Moving all the nulls to the end is an arbitrary decision. Clients should be able to pass in their own Comparator into sort. They can then decide how to handle nulls themselves.

It's unclear to me that there's any performance benefit on sorting out the nulls first vs. doing it in the Comparator.

moveNullsToEnd and swap are both methods that act on an array, and have no special relationship to sorting algorithms. Either you don't want to expose them for use elsewhere, and they should be private, or you want to expose them and they should be in a different, more appropriate utility class.

It would be preferable if all your methods used generics for consistency with the rest of the API, rather than switching back and forth between Object and T.

If this is intended for real use, it would be nice to have multiple different methods with reasonable defaults, such as in Arrays.sort() and Collections.sort().

Implementation

Since you're not promising a stable sort, moveNullsToEnd is way more complex than it needs to be. Walk the array once. Every time you see a null, swap it with the last non-null value. Alternately, if you want a stable sort in-place, walk the array once with two counters, a write index and a read index. Every time you see a null, increment the read an extra time. Otherwise, move from the read index to the write index. When read reaches the end, write nulls the rest of the way.

moveNullsToEnd fails on an array with only null elements.

Don't leave commented-out code in your codebase. Use a logger if you need to and remove it.

The quickSort method doesn't perform a quicksort, but rather an amalgam of quicksort and insertion sort. It's not by accident that the java library methods are labeled the generic sort.

insertionSort would be easier to read with a while loop and a decrement inside it, mostly due to the complex comparison which eats most of the for declaration. The j-- gets lost at the end. Better from a performance standpoint would be @vnp's recommendation.

I don't feel like getting too deep into the weeds of sorting implementations, so I'm going to leave it there. Below find stable and unstable implementations of moveNullsToEnd.

private static <T> int moveNullsToEndStable(final T[] array) {
int writeIndex = 0;

continue;
}
writeIndex++;
}

final int returnValue = writeIndex;
for ( ; writeIndex < array.length; writeIndex++) {
array[writeIndex] = null;
}

return returnValue;
}

• I don't think your moveNullsToEndUnstable works. In the case where there's a null in the middle of the array and also at the end (back) then the first swap does nothing, leaving the array as it was. This would break the rest of the code and the constraint of actually moving nulls to the end. The second while loop in my version is there to find the first non-null element at the end of the array. Aug 20, 2019 at 14:16
• @markspace Yes, that was an oversight. I corrected the posted code. Though it's now closer in visual complexity to your original, I still think there's value in not having nested loops. Aug 20, 2019 at 14:27
• Still doesn't work, unfortunately. Your code now finds the first non-null at the end of the array, but there's no guarantee that the value after that first non-null will also be non-null. For each null value found in the front, you must find a non-null to swap it with. The nested loops are required for correctness. (Part of the reason some of these routines are public is that I did test them rather extensively. Nested loops are required here, I'm pretty sure of that.) Aug 20, 2019 at 14:39
• Yeah, on reflection, I believe you are correct. You always have to worry about null-null pairings. Boo! Aug 20, 2019 at 14:48
• Other than that sanfu, it was an good review. Thanks! Aug 20, 2019 at 14:53

I don't know how to read java code (I'm a python person), but reading your post, I have a few suggestions for you. (Sorry if you have already done these, as I've said I don't know java.)

1. It sounds like you are doing median of 9 every single time. I'd suggest doing median of 3 if the list size is less than 128, and if it's between 128-8192, median of 9 (evenly spread out), and if the list size is greater than 8192, median of 27, or whatever odd number you like. EDIT: considering this again, I'd suggest you use bit_length instead. It adapts for much larger lists, and for smaller lists too.
2. This might not be an improvement, but it's worth a try. If the pivot was horrible (the size of lst1 was more than 8x or less than 1/8 of the size of lst2), you can choose a random pivot instead. This will guarantee that you will not go to O(N^2) time.
3. If you really care about improving your time, you can consider using sorting networks instead of insertion sort because they are up to 2x faster.

That's it for now. I might edit it again later.

• Regarding using a median of 3 for sizes of 127 or less, or using a median of 27 for sizes over 8192: have you tested these ideas? Do they work? About what speed improvements do you measure? Mar 23, 2021 at 14:49
• Yes, I have tested these ideas. They do work, they gave me about a 5-10% improvement on my computer. However, I think using the median of [double length of binary representation of length of list minus 1] evenly spread out values in the list would be best. It adapts for different size lists without more if statements, and is quite simple. Mar 23, 2021 at 18:45