Taking the Last Element as Pivot on Sorted Input

A quicksort that always takes the last item of the range as its pivot takes O(n²) time on input that is already sorted, as slow as an elementary sort, because every pivot is the largest item in its range. This card shows the symptom, the trigger, why it happens, what it costs and the fix.

The symptom is a sort that is correct, fast in testing on shuffled data, and then slow on data that arrives sorted or nearly sorted, such as records appended in time order and sorted by time again. In Python it can crash outright. A run of a recursive last-item quicksort finished on 500 sorted numbers and stopped with a RecursionError on 1,000, because Python allows 1,000 nested calls by default and the sort needed one call for every item.

The trigger is the input's order meeting a fixed pivot position. An instrumented quicksort counted its comparisons and its deepest chain of calls that partitioned something, first with the last item as pivot, then with a pivot chosen at random by a generator seeded with 42.

The mechanism is that on sorted input the last item of every range is its largest. The partition compares every other item with it, finds them all smaller, and leaves the pivot where it is, so the left side holds everything else and the right side is empty. The next call does the same to a range one item shorter. The partitions compare 7 + 6 + … + 1 = 28 items for n = 8, and n(n − 1)/2 in general, 499,500 for n = 1,000, with one call open for every item. Reversed input fails the same way with the pivot always the smallest. Eight equal items fail too, though no pivot looks badly chosen: the Lomuto scheme sends items equal to the pivot to its right, so every partition again leaves one side empty.

The cost is a sort that is O(n²) on exactly the inputs real data tends to have: sorted, nearly sorted, or full of repeated keys. For a million items, n(n − 1)/2 is about 500 billion comparisons, against about 20 million for n log₂ n. And because the input decides it, anyone who can choose your input can choose the slow case.

The remedy is to choose the pivot uniformly at random from the range and swap it to the end before partitioning, which leaves the partition itself unchanged. With seed 42 the run made 16 comparisons on 1 to 8 and 10,635 on 1 to 1,000, and no input is slow every time. Taking the median of the first, middle and last items also fixes sorted and reversed input, but an input built for the purpose can still defeat it. For many repeated keys the fix is a three-way partition, which gathers the items equal to the pivot into a middle band that no later call touches.