Quicksort with Insertion Sort and Improved Pivot Selection

Question

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.

That's it, please enjoy.

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.

Answer 1

• 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.

Answer 2

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

Readability

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;

    for (int readIndex = 0; readIndex < array.length; readIndex++) {
        if (array[readIndex] == null) {
            continue;
        }
        array[writeIndex] = array[readIndex];
        writeIndex++;
    }

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

    return returnValue;
}

Answer 3

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.