Integer quicksort in Java 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 &lt; 2) {
            return;
        }

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

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

            if (current &gt; pivot) {
                ++rightPartitionLength;
                int tmp = array[toIndex - rightPartitionLength];
                array[toIndex - rightPartitionLength] = current;
                array[index] = tmp;
            } else if (current &lt; 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(&quot;Seed: &quot; + seed);
        long startTime = System.nanoTime();
        sort(array1, FROM, TO);
        long endTime = System.nanoTime();

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

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

        System.out.printf(&quot;Arrays.sort in %.2f milliseconds.\n&quot;,
                          (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 &lt; 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.
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 &gt; pivot) {
    ++rightPartitionLength;
    swap(array, toIndex - rightPartitionLength, index);
} else if (current &lt; 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 &lt; 2) {
            return;
        }

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

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

            if (current &gt; pivot) {
                ++rightPartitionLength;
                int tmp = array[toIndex - rightPartitionLength];
                array[toIndex - rightPartitionLength] = current;
                array[index] = tmp;
            } else if (current &lt; 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;
    }

}