Your quicksort is slowestslowest on already-sorted data

It sounds like a typo. Sorting something that is already sorted should be the easy case - and for merge sort, insertion sort and every intuition you have, it is. For textbook quicksort it is the catastrophe. Here is why, measured rather than asserted, and the one-line fix.

What just happened

With the last element as the pivot, a thousand shuffled items cost about 11,000 comparisons at a recursion depth around 21. Switch the input to sorted and the same code does roughly 499,500 comparisons at a depth of 999 - about 45 times the work, on input that looks easier.

Now flip the pivot to random and watch sorted input drop straight back to the shuffled numbers. Nothing about the data changed. The only thing that changed is which element the algorithm picked to compare against.

The mechanism

Quicksort works by picking a pivot and moving everything smaller to its left and everything larger to its right. The pivot is then in its final position forever, and the algorithm recurses into the two sides. Its speed depends entirely on one assumption: that those two sides are roughly equal.

On sorted input with a last-element pivot, that assumption collapses. The pivot is always the largest value left, so everything goes to the left side and the right side is empty. Instead of halving the problem, each step removes exactly one element - and n levels of n work is the definition of quadratic.

int partition(int[] a, int lo, int hi) {
    int pivot = a[hi];        // <- on sorted input, always the LARGEST
    int i = lo;
    for (int j = lo; j < hi; j++) {
        if (a[j] < pivot) { swap(a, i, j); i++; }
    }
    swap(a, i, hi);
    return i;                 // ...so this lands at hi, every single time
}

The recursion depth is the part that turns a performance article into an incident report. Depth 999 means 999 stack frames alive at once. Feed the same code a sorted array of a hundred thousand elements and you do not get a slow sort, you get a StackOverflowError.

Why this bites in production, not in tests

Here is the cruel part. Test fixtures are usually small and hand-made. Real data arrives sorted constantly: rows from a database with an ORDER BY, auto-incrementing ids, timestamps, anything already processed by an earlier sorted step, or a list a user just sorted by clicking a column header.

So the naive implementation passes every test, ships, and falls over on the most ordinary input in the system. Worse, it is not a crash you can easily reproduce locally, because locally your fixture had eight rows in a random order.

The fix is one line

Do not let the input choose the pivot. Swap a random element into the pivot position before partitioning, and sorted input stops being special - an adversary would have to predict your random numbers.

int partition(int[] a, int lo, int hi) {
    int k = lo + random.nextInt(hi - lo + 1);
    swap(a, k, hi);           // <- the whole fix
    int pivot = a[hi];
    ...
}

Median-of-three - taking the median of the first, middle and last elements - is the other common answer, and it has the advantage of being deterministic. Production libraries go further still: introsort monitors the recursion depth and switches to heapsort when it grows too far, which caps the worst case at O(n log n) rather than merely making it unlikely.

The lesson underneath

Average-case complexity is a statement about a distribution of inputs, not a promise about yours. Quicksort is O(n log n) on average and O(n squared) in the worst case, and the gap between those two is not an academic footnote - it is the difference between a page that loads and a stack trace.

Whenever you read that an algorithm is fast "on average", the useful question is: what does the bad case look like, and does my real data look like that? For quicksort the bad case is sorted data, and sorted data is everywhere.

Common questions