Quicksort WAY slower than Insertion and Selection Sort in Java?

Question

So I'm brushing up on my algorithms knowledge and testing runtimes of different sorts, and I've found that my implementation of quicksort is much, much slower than even insertion and selection sorts. The algorithm looks right to me, and it looks identical in practice to several other implementations I found online. But it has to be wrong somehow, because it's on the order of 500x slower than the O(N^2) sorts. Timing the sorts on 3 (deep) copies of a randomized 10000 element array gives:

Insertion Sort: (75355000 ns)

Selection Sort: (287367000 ns)

Quick Sort: (44609075000 ns)

Here's the code:

public static void quickSort(Thing [] theThings, int left, int right) {
    int i= left; int j = right;
    int pivot = theThings[(int)(left + (right-left)*0.5)].getValue();

    while (i <= j) {
        while (theThings[i].getValue() < pivot)
            i++;
        while (theThings[j].getValue() > pivot)
            j--;

        if (i <= j) {
            Thing temp = theThings[i];
            theThings[i] = theThings[j];
            theThings[j] = temp;

            i++;
            j--;
        }

        if (left < j)
            quickSort(theThings, left, j);
        if (right > i)  
            quickSort(theThings, i, right);
    }                   
}

The Thing class is just a dummy I made to play with in my algorithms. It has an integer value generated by Random in the constructor, and not much else.

I've verified that the quicksort does correctly sort the array - just much slower than it should. I've tried different pivot choosing methods. I've tried everything I could think of. Maybe I'm just too close to see it, but could anyone tell me what is killing my algorithm?

Answer 1

You should be recursing to quicksort each part of the array after the while loop is complete, not each time through the while loop.