Recursive partition sort is inefficient

Question

I have written a recursive method for a partition sort that sorts the array. However, when I use an array of more than 10-20 elements the program takes a really long time to complete. (On my computer a bubble sort of a 100,000 int array will take about 15-20 seconds, but with an array of only 30 ints my partition sort is taking around 45 seconds to be sorted.)

public static int[] partitionSortRecursive(int[] array, int beginning, int end)
{
    if (end < beginning)
        return array;

    int pivot = (array[beginning] + array[end]) / 2;
    int firstUnknown = beginning;
    int lastS1 = beginning - 1;
    int firstS3 = end + 1;

    while (firstUnknown < firstS3)
    {
        if (array[firstUnknown] == pivot)
        {
            firstUnknown++;
        }
        else if (array[firstUnknown] > pivot)
        {
            firstS3--;
            int temp = array[firstUnknown];
            array[firstUnknown] = array[firstS3];
            array[firstS3] = temp;
        }   
        else
        {
            lastS1++;
            int temp = array[firstUnknown];
            array[firstUnknown] = array[lastS1];
            array[lastS1] = temp;
            firstUnknown++;
        }

    }

    partitionSortRecursive(array, 0, lastS1);
    partitionSortRecursive(array, firstS3, end);

    return array;
}

Answer 1

Your code at the current state looks very slow. Partition sort (or quicksort as it is generally known) is supposed to be faster than Bubble Sort. With my quicksort and bubble sort code, here is what I get for a 1000-element array:

Time taken (ns): 612535
Sorted List: ...
Time taken (ns): 5819902
Sorted List: ...

This is because quicksort is \$O(n \log n)\$ while bubble sort is \$O(n^2)\$.

How I would do quicksort:

1. Select a pivot
2. Create two pointers, one at the front and one at the back
3. Move first pointer up until there is a value greater or equal to the pivot
4. Move second pointer down until there is a value less than or equal to the pivot
5. Swap and advance both pointers
6. If the pointers have not passed each other, go to step 1. Otherwise, continue
7. Repeat recursively for each subarray

Code:

private static final Random RANDOM = new Random();

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

private static void quickSort(int[] array, int begin, int end) {
    if (end - begin < 2) {
        return;
    }
    if (end - begin == 2) {
        // Optimization: array length 2
        if (array[begin] > array[end - 1]) {
            swap(array, begin, end - 1);
        }
        return;
    }
    int splitIndex = partition(array, begin, end);
    quickSort(array, begin, splitIndex);
    quickSort(array, splitIndex, end);
}

private static int partition(int[] array, int begin, int end) {
    int pivot = array[RANDOM.nextInt(end - begin) + begin];
    begin--;
    while (begin < end) {
        do {
            begin++;
        } while (array[begin] < pivot);
        do {
            end--;
        } while (array[end] > pivot);
        if (begin < end) {
            // Make sure they haven't crossed yet
            swap(array, begin, end);
        }
    }
    return begin; // TODO check
}

private static void swap(int[] array, int begin, int end) {
    int temp = array[begin];
    array[begin] = array[end];
    array[end] = temp;
}

The results:

Time taken (ns): 507845
Sorted Array: ...

Answer 2

Two mistakes

There are two mistakes that I identified:

1. You recurse at 0 instead of beginning. In other words, this line:

   partitionSortRecursive(array, 0, lastS1);
   

   should be:

   partitionSortRecursive(array, beginning, lastS1);
   

2. Your pivot could overflow:

   int pivot = (array[beginning] + array[end]) / 2;
   

   Here, pivot could become negative if the two values added together overflowed an int. You could use a long to do the averaging, but I suggest just picking a pivot like this:

   int pivot = array[beginning];
   

Answer 3

I have one suggestion with regards to time complexity -

• If the list is too long, You can limit the recursive calls by setting limit to some value 'k'.
• Then use the "Insertion sort" when the recursion reached to this limit in QuickSort. QuickSort is not efficient when the list gets smaller.
• QuickSort can quickly lead to worst case complexity for larger list with unbalanced partition which depends on selection of pivot element.

Answer 4

I rearranged the code to be more readable for myself.

Replaced "0" by "beginning"; "pivot" is calculated as "long" and cast to "int" after division so it should not overflow ((Integer.MAX_VALUE + Integer.MAX_VALUE) / 2 = Integer.MAX_VALUE). Credit to JS1.

"temp"'s value is needed in every case and seemed redundant and complex to read to me so I moved these lines of the (almost) same code up a few lines -> eliminated duplicate code.

One "if" was removed. An operation happend in "less-than" and "equals" which was moved to the end because it was not relevant when exactly firstUnknown++ happens - it just may not happen in the "greater-than" clause. I think it is more readable using "less-than" and "greater-than" instead of "equals", "greater-than" and "else".

public static int[] partitionSortRecursive(int[] array, int beginning, int end)
{
if (end < beginning) {
    return array;
}

int pivot = (int) (((long) array[beginning] + (long) array[end]) / 2);
int firstUnknown = beginning;
int lastS1 = beginning - 1;
int firstS3 = end + 1;

while (firstUnknown < firstS3) {
    int temp = array[firstUnknown];
    if (temp > pivot) {
        firstS3--;
        array[firstUnknown] = array[firstS3];
        array[firstS3] = temp;
        continue;
    } else if (temp < pivot) {
        lastS1++;
        array[firstUnknown] = array[lastS1];
        array[lastS1] = temp;
    }
    firstUnknown++;
}

partitionSortRecursive(array, beginning, lastS1);
partitionSortRecursive(array, firstS3, end);

return array;
}

Answer 5

This is quite non-standard way of choosing a pivot value:

    int pivot = (array[beginning] + array[end]) / 2;

It may yield a value which does not exist in the array being sorted. That should not hurt, as the value usually should be between values of array[beginning] and array[end], so at worst your 3-way partitioning would become 2-way.

However, if both terms of a sum are positive and big (say, bigger than INT_MAX/2), they may add up to a value greater than the int type range limit, which will cause an arithmetic overflow and can yield pivot < 0. That can lead to a 1-way partitioning and an 'infinite recursion' which would end with a memory overflow. (Same scenario may happen for two negative values, big wrt. an absolute value, say less than -INT_MIN/2.)

It is much better to choose a pivot value from those existing in your array. That guarantees at least one item per recursion level goes to its final position, so the whole process will stop eventually.

It is also way easier in a general case, because arithmetics on integer indices is quite well-defined, which needn't apply to array items. Suppose, for example, sorting an array of strings – how would you compute a sum (array[beginning] + array[end]) if array[beginning] is "Los Angeles" while array[end] is "Tokyo"...? And how are you going to divide that sum by 2...?