Integer quicksort in Java

Question

I have this Quicksort implementation that sorts arrays of int (not Integer). It has comparable performance to Java's DualPivotQuicksort, especially when the size of the range is below one million elements or so.

IntegerQuicksort.java

package net.coderodde.util;

import java.util.Arrays;
import java.util.Random;

public class IntegerQuicksort {

    public static void sort(int[] array) {
        sort(array, 0, array.length);
    }

    public static void sort(int[] array, int fromIndex, int toIndex) {
        if (toIndex - fromIndex < 2) {
            return;
        }

        int pivot = array[fromIndex];
        int leftPartitionLength = 0;
        int rightPartitionLength = 0;
        int index = fromIndex;

        while (index < toIndex - rightPartitionLength) {
            int current = array[index];

            if (current > pivot) {
                ++rightPartitionLength;
                int tmp = array[toIndex - rightPartitionLength];
                array[toIndex - rightPartitionLength] = current;
                array[index] = tmp;
            } else if (current < pivot) {
                int tmp = array[fromIndex + leftPartitionLength];
                array[fromIndex + leftPartitionLength] = current;
                array[index] = tmp;

                ++index;
                ++leftPartitionLength;
            } else {
                ++index;
            }
        }

        sort(array, fromIndex, fromIndex + leftPartitionLength);
        sort(array, toIndex - rightPartitionLength, toIndex);
    }

    private static final int SIZE = 500_000;
    private static final int FROM = 100;
    private static final int TO = SIZE - 100;

    public static void main(final String... args) {
        long seed = System.nanoTime();
        Random random = new Random(seed);
        int[] array1 = getRandomArray(SIZE, -1000, 1000, random);
        int[] array2 = array1.clone();

        System.out.println("Seed: " + seed);
        long startTime = System.nanoTime();
        sort(array1, FROM, TO);
        long endTime = System.nanoTime();

        System.out.printf("IntegerQuicksort.sort in %.2f milliseconds.\n",
                          (endTime - startTime) / 1e6);

        startTime = System.nanoTime();
        Arrays.sort(array2, FROM, TO);
        endTime = System.nanoTime();

        System.out.printf("Arrays.sort in %.2f milliseconds.\n",
                          (endTime - startTime) / 1e6);

        System.out.println(Arrays.equals(array1, array2));
    }

    public static int[] getRandomArray(int size, 
                                       int minimum, 
                                       int maximum, 
                                       Random random) {
        int[] array = new int[size];

        for (int i = 0; i < size; ++i) {
            array[i] = random.nextInt(maximum - minimum + 1) + minimum;
        }

        return array;
    }
}

Some performance figures:

Seed: 347202193766632
IntegerQuicksort.sort in 61.21 milliseconds.
Arrays.sort in 131.72 milliseconds.

I am well aware that the current pivot selection rule will make the algorithm degrade to quadratic running-time on sorted input; please ignore this, I wanted to experiment a little bit.

So, is there room for improvement? Naming? Coding style? Please, tell everything that comes to mind.

Answer 1

First of all, your benchmark is not really correct because it doesn't take into account any VM warmup and has only a single iteration.

Using JMH 1.11.3, I rewrote your benchmark: two integer arrays of length 10.000, 100.000, 1.000.000 and 10.000.000 are created with random values and then sorted with your implementation and Arrays.sort. The results are (Windows 10, JDK 1.8.0_66 64 bits, i5-3230M CPU @ 2.60GHz):

Benchmark            (length)  Mode  Cnt     Score    Error  Units
SortTest.arraysSort     10000  avgt   30     0,557 ±  0,015  ms/op
SortTest.arraysSort    100000  avgt   30     7,369 ±  0,267  ms/op
SortTest.arraysSort   1000000  avgt   30    86,435 ±  3,273  ms/op
SortTest.arraysSort  10000000  avgt   30  1039,120 ± 49,706  ms/op
SortTest.customSort     10000  avgt   30     0,905 ±  0,029  ms/op
SortTest.customSort    100000  avgt   30    11,152 ±  0,391  ms/op
SortTest.customSort   1000000  avgt   30   132,986 ±  5,581  ms/op
SortTest.customSort  10000000  avgt   30  1530,132 ± 42,771  ms/op

This shows that while Arrays.sort is indeed a little faster, your implementation has a very good performance, for small and large arrays.

---

I find your code is really good and easy to read. Only a few remarks if you intent to keep this code around:

• The method sort(int[] array, int fromIndex, int toIndex) does not do any sanity checks on fromIndex and toIndex. This is well understandable because it introduces another level of complexity. You should then consider making that method private instead of public: this way, you ensure that no out of bounds exception can occur through the public API.
• Consider perhaps renaming the utility class IntQuicksort to make it clear that is operates on primitive int array and not Integer objects. Also, since this is a utility class, consider making it final and adding a private constructor.

• Regarding the code itself, I would add a swap method to refactor the code a little

  private static void swap(int[] array, int firstIndex, int secondIndex) {
      int tmp = array[firstIndex];
      array[firstIndex] = current;
      array[secondIndex] = tmp;
  }
  

  and use it like

  if (current > pivot) {
      ++rightPartitionLength;
      swap(array, toIndex - rightPartitionLength, index);
  } else if (current < pivot) {
      swap(array, fromIndex + leftPartitionLength, index);
      ++index;
      ++leftPartitionLength;
  }
  

---

Code of benchmark for completeness:

import java.util.Arrays;
import java.util.concurrent.ThreadLocalRandom;
import java.util.concurrent.TimeUnit;

import org.openjdk.jmh.annotations.Benchmark;
import org.openjdk.jmh.annotations.BenchmarkMode;
import org.openjdk.jmh.annotations.Fork;
import org.openjdk.jmh.annotations.Level;
import org.openjdk.jmh.annotations.Measurement;
import org.openjdk.jmh.annotations.Mode;
import org.openjdk.jmh.annotations.OutputTimeUnit;
import org.openjdk.jmh.annotations.Param;
import org.openjdk.jmh.annotations.Scope;
import org.openjdk.jmh.annotations.Setup;
import org.openjdk.jmh.annotations.State;
import org.openjdk.jmh.annotations.Warmup;

@Warmup(iterations = 10, time = 700, timeUnit = TimeUnit.MILLISECONDS)
@Measurement(iterations = 10, time = 700, timeUnit = TimeUnit.MILLISECONDS)
@BenchmarkMode(Mode.AverageTime)
@OutputTimeUnit(TimeUnit.MILLISECONDS)
@Fork(3)
public class SortTest {

    @State(Scope.Benchmark)
    public static class ArrayContainer {

        @Param({ "10000", "100000", "1000000", "10000000" })
        private int length;

        private int[] array;
        private int[] arrayToSort;

        @Setup(Level.Iteration)
        public void setUp() {
            ThreadLocalRandom random = ThreadLocalRandom.current();
            array = random.ints(length).toArray();
        }

        @Setup(Level.Invocation)
        public void cloneArray() {
            arrayToSort = array.clone();
        }

    }

    public static void sort(int[] array) {
        sort(array, 0, array.length);
    }

    public static void sort(int[] array, int fromIndex, int toIndex) {
        if (toIndex - fromIndex < 2) {
            return;
        }

        int pivot = array[fromIndex];
        int leftPartitionLength = 0;
        int rightPartitionLength = 0;
        int index = fromIndex;

        while (index < toIndex - rightPartitionLength) {
            int current = array[index];

            if (current > pivot) {
                ++rightPartitionLength;
                int tmp = array[toIndex - rightPartitionLength];
                array[toIndex - rightPartitionLength] = current;
                array[index] = tmp;
            } else if (current < pivot) {
                int tmp = array[fromIndex + leftPartitionLength];
                array[fromIndex + leftPartitionLength] = current;
                array[index] = tmp;

                ++index;
                ++leftPartitionLength;
            } else {
                ++index;
            }
        }

        sort(array, fromIndex, fromIndex + leftPartitionLength);
        sort(array, toIndex - rightPartitionLength, toIndex);
    }

    @Benchmark
    public int[] customSort(ArrayContainer container) {
        sort(container.arrayToSort);
        return container.arrayToSort;
    }

    @Benchmark
    public int[] arraysSort(ArrayContainer container) {
        Arrays.sort(container.arrayToSort);
        return container.arrayToSort;
    }

}

Answer 2

• No naked loops

  The while loop implements an important algorithm, known as partition, and deserves to have a name. I recommend to factor it out into a method

  int partition(int [] array, int fromIndex, int toIndex);
  

  returning a partition point.

• Tail recursion

  AFAIK Java doesn't optimize tail recursive calls. You may want to eliminate second call to sort manually.

• Indices vs lengths

  It seems that operating on partition boundaries instead of lengths may simplify the code. Mostly matter of taste I suppose.

Otherwise, LGTM.

Answer 3

Implementation details:

Instead of using the length of each side of the partition it would be simpler to just to keep track of the index of the boundary. Also a swap function would make your code more readable.

     public static void  swap(int x, int y, int[] array) 
     {       
         int tmp = array[x];
         array[x] = array[y];
         array[y] = tmp;
     }

You would end with something like this:

   public static void sort(int[] array, int fromIndex, int toIndex) 
   {
        if (toIndex - fromIndex < 2) return;

        int l = fromIndex; 
        int g = toIndex;    
        int i = l + 1;
        int pivot = l;        
        while (i < g)
        {
            if (array[i] < pivot)
                swap(i++, l++, array);
            else if (array[i] > pivot)
                swap(i, --g, array);
            else
                i++;
        }

        sort(array, fromIndex, l);
        sort(array, g, toIndex);
  }

---

Also if java 8 is available you can change this function:

public static int[] getRandomArray(int size, 
                                       int minimum, 
                                       int maximum, 
                                       Random random) {

       int[] array = new int[size];

        for (int i = 0; i < size; ++i) {
            array[i] = random.nextInt(maximum - minimum + 1) + minimum;
        }

        return array;
    }

to:

 public static int[] getRandomArray(int size, 
                                       int minimum, 
                                       int maximum, 
                                       Random random) {     
     return random.ints(minimum, maximum + 1)
                  .limit(size)
                  .toArray();
 }

Partition algorithm :

This seams to be Dijkstra's 3-way partitioning, a better 3 way partitioning would be Bentley-Mcilroy's (is similar to Hoare's and unlike Dijkstra's it doesn't do extra swaps if there are no repeated pivot elements). For more information check this: QUICKSORT IS OPTIMAL.

Recursion:

You could avoid recursion using a stack (unboxing and autoboxing could make tail recursion a better choice though). Also by always pushing the smallest range into the stack you ensure that at any given time the number of ranges inside it are at most lg(n).

NOTE: Creating a fixed size int Stack would give you the best performance. You can use the fixed size 2*log2(n).

public static void sort(int[] array, int fromIndex, int toIndex) 
{

    Stack<Integer> stack = new Stack<>();
    stack.push(null);
    stack.push(null);
    while (!stack.empty()) 
    {
        while (fromIndex < toIndex - 1) 
        {
            int l = fromIndex;
            int g = toIndex;
            int i = l + 1;
            int pivot = l;
            while (i < g) 
            {
                if (array[i] < pivot) 
                    swap(i++, l++, array);
                else if (array[i] > pivot) 
                    swap(i, --g, array);
                else 
                    i++;
            }
            if ((l - fromIndex) > (toIndex - g)) 
            {
                stack.push(l);
                stack.push(fromIndex);
                fromIndex = g;
            } 
            else 
            {
                stack.push(toIndex);
                stack.push(g);
                toIndex = l;
            }

        }
        fromIndex = stack.pop();
        toIndex = stack.pop();
    }

}