A simple quicksort implementation

Question

I have the following class for Quicksorting.

import java.util.Random;

public class QuickSorter {
    public static void main(String[] args) {
        Random random = new Random();
        int[] randoms = new int[10000];
        for(int i = 0; i < randoms.length; i++) randoms[i] = random.nextInt(10000);

        quickSort(randoms, 0, randoms.length);
        System.out.println(Arrays.toString(randoms));
    }

    /** Same as {@link #quickSort(int[], int, int)}, but assumes the whole array should be sorted. */
    public static void quickSort(int[] in) {quickSort(in, 0, in.length);}
    /** Sorts an array of integers using the Quicksort algorithm, in the range [{@code start}, {@code end}).
     * @param in The full array to sort
     * @param start The starting index, inclusive
     * @param end The ending index, exclusive
     * @see #quickSort(int[]) */
    public static void quickSort(int[] in, int start, int end) {
        int pivot = (start + end) / 2;

        /* Temporary array containing the ordered sub-list */
        int[] sub = new int[end - start];
        int left = 0, right = sub.length;

        /* Populate the sub-list */
        for(int i = start; i < end; i++) {
            if(i == pivot) continue;

            if(in[i] < in[pivot]) {
                sub[left++] = in[i];
            } else {
                sub[--right] = in[i];
            }
        }
        /* Add in the original pivot in its new position */
        sub[left] = in[pivot];

        /* Copy back into the original array */
        for(int k = start; k < end; k++) {
            in[k] = sub[k - start];
        }

        /* Translate new pivot position into full list index */
        left += start;
        if(left - start > 0) quickSort(in, start, left);
        /* The start of the right branch should not include the pivot */
        left++;
        if(end - left > 0) quickSort(in, left, end);
    }
}

Is this the most efficient way to Quicksort? I feel as if copying the values from sub back into in can be done better somehow.

And of course, I know this won't cause any huge issues with arrays of size 10000. But, I'd like this to hold up all the way up to 2^31-1 (to the limits of max array size).

Answer 1

Integer overflow

Since you said you cared about array sizes up to the max size, you should know that this line could cause an overflow with two large indices, meaning that pivot could become negative:

    int pivot = (start + end) / 2;

You can fix this by using the following expression instead:

    int pivot = start + (end - start) / 2;

Skip subarrays of length 1

You can do slightly better by ignoring subarrays of length 1, since they are already sorted. In other words, this line:

    if(left - start > 0) quickSort(in, start, left);

could be:

    if(left - start > 1) quickSort(in, start, left);

The same goes for the right subarray.

In-place version should be faster

Although there is nothing incorrect with your version, it allocates a temporary array and copies elements back and forth. If you switched to an in-place algorithm, you will reduce your array writes by 50%. This means that the in-place version should be faster than your current version, assuming you use a proper version that swaps elements from both ends working inwards.

Answer 2

This implementation will exhibit \$O(N^2)\$ performance when all the array elements are the same.

Consider what happens in this loop when all the array elements are the same:

for(int i = start; i < end; i++) {
    if(i == pivot) continue;

    if(in[i] < in[pivot]) {
        sub[left++] = in[i];
    } else {
        sub[--right] = in[i];
    }
}

in[i] < in[pivot] will never be true, so at the end of the loop left will be 0.

left += start;
if(left - start > 0) quickSort(in, start, left);
/* The start of the right branch should not include the pivot */
left++;
if(end - left > 0) quickSort(in, left, end);

Since left is 0 when this bit of code is run, we just call quickSort(in, start + 1, end), so the sequence of calls will look like

quickSort(in, 0, end)
quickSort(in, 1, end)
quickSort(in, 2, end)
...
quickSort(in, end - 1, end)

With a big enough input array (10,000 elements did the trick on ideone), this will result in a stack overflow.

The site for Algorithms, 4th Edition has a good discussion about this issue and provides an implementation that avoids this problem.

There's also some good discussion of partitioning in Quicksort Partitioning: Hoare vs. Lomuto.