# Recursive partition sort is inefficient

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;
}

• the first recursive call doesn't pass beginning as I would expect – ratchet freak Jan 5 '15 at 9:34

## 5 Answers

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


# 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];

• Selecting pivot element as the beginning could lead to unbalance recursive call, its recommended to use the middle (as mostly the list would be avg sorted or based on mean of 1st, last and middle elem.) right? – JustVirtually Nov 7 '15 at 22:44
• @RsN_Spartan Yes, you are correct. I didn't bother mentioning the superior choices because these issues are already well known. – JS1 Nov 7 '15 at 22:55

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.

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;
}

• In your future edit, please also add what changes you made in the code and explain why do you feel these changes make a better review! :) You'll help to OP much more this way and you'll get more upvotes :p – IEatBagels Oct 22 '15 at 13:04
• @TopinFrassi It seems I was wrong that it might have helped anyone that I posted an answer that was not explaining everything (just because it was possible in my time frame to write what came to my mind instanlty and not thinking about possible errors in my own answer). – Johannes Jan 12 '16 at 16:40

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.