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

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:

• Select a pivot

• Create two pointers, one at the front and one at the back

• Move first pointer up until there is a value greater or equal to the pivot

• Move second pointer down until there is a value less than or equal to the pivot

• Swap and advance both pointers

• If the pointers have not passed each other, go to step 1. Otherwise, continue

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

StackExchange Code Review Q#75687, answer score: 5