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 &lt; beginning)
        return array;

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

    while (firstUnknown &lt; firstS3)
    {
        if (array[firstUnknown] == pivot)
        {
            firstUnknown++;
        }
        else if (array[firstUnknown] &gt; 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 &lt; 2) {
        return;
    }
    if (end - begin == 2) {
        // Optimization: array length 2
        if (array[begin] &gt; 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 &lt; end) {
        do {
            begin++;
        } while (array[begin] &lt; pivot);
        do {
            end--;
        } while (array[end] &gt; pivot);
        if (begin &lt; 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: ...