A simple quicksort implementation

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

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.

StackExchange Code Review Q#110966, answer score: 5