Empirical complexity

Quicksort

Choose a pivot, move everything smaller than it to the left and everything larger to the right, and then sort the two sides the same way. If the pivot lands near the middle the two sides are half the size and there are log n levels, as in merge sort. If it lands at one end, one side is empty and the other is one shorter, so there are n levels of a scan that is n long — and the pivot used here is the last element, which on sorted or reversed input is always an end. The curve plots comparisons, which is what every textbook bound for a sort is about and what makes the four of them directly comparable. The moves are counted too and shown in the panel beside it — worth a look on merge sort, whose comparison count hides the fact that it touches every element on every level.

The claim being tested

O(n log n) shuffled · O(n²) sorted or reversed

When it is the right choice

It is the default in-place sort in most standard libraries, because its average case has a smaller constant factor than merge sort’s and it needs no scratch array. Real implementations avoid the worst case rather than accept it: a median-of-three or a randomised pivot makes the adversarial input vanishingly unlikely, and several switch to heapsort if the recursion gets too deep. The plain last-element pivot is kept here precisely so the worst case is reachable.

How it works

• Take the last element of the range as the pivot.
• Sweep the range, moving every element smaller than the pivot to the front.
• Swap the pivot into the gap between the two groups; it is now in its final place.
• Sort the two groups the same way.
• Count one comparison per element swept and two moves per swap.

Worth noticing

• Switch the shape from shuffled to already sorted — the second preset does it — and the curve changes class in front of you: gradient just above 1 becomes gradient 2. Nothing about the code changed. This is the clearest demonstration in the suite that a complexity claim is a claim about an algorithm *and its input*.
• On sorted input the sweep swaps on every single comparison, because every element it looks at is smaller than the pivot — so the move counter beside the plot reads twice the comparison count, and the total work is three times it. That is also why the first cost estimate written for this page was wrong by a factor of three, and was corrected by comparing it against a real count.
• Put the sorted-input curve on the same axes as selection sort and they coincide exactly: both make n(n−1)/2 comparisons, 8,386,560 of them at n = 4,096. Two algorithms in different complexity classes, on one input, doing identical work.
• The implementation recurses on the smaller partition and loops on the larger. That keeps the recursion two deep on sorted input instead of n deep, which is the only reason the adversarial case can be measured at 4,096 at all — recursing on both overflows the JavaScript stack at about 6,000.

Cost

Best

O(n log n)

Average

O(n log n)

Worst

O(n²)

Extra space

O(log n)

n is

the length of a list of numbers

Measures

shuffled: up to n = 131,072; sorted: up to n = 4,096; reversed: up to n = 4,096

The ceilings are a time limit rather than a memory one, which makes this tool the odd one out in the suite. Its recorded steps are tiny — one step per measured size, not one per operation — so nothing about the trace would ever stop a run. What has to be stopped is the measuring itself: a configuration that would take more than forty million operations to count is refused before a single one of them is counted, from a formula in the input sizes rather than by starting and giving up. Two further limits sit beside it that no formula in operations can see: building the input is real work, and a recursion n deep overflows the call stack long before its operation count becomes interesting.

A fit over a dozen sizes is evidence and not proof. It cannot rule out a term that only begins to matter past the largest size measured, and it says nothing at all about the constant factors that decide which of two algorithms in the same class is actually faster on a real machine.

Worth comparing

• Merge sort — The same average class with no worst case to avoid, which is the trade this page is one half of.
• Selection sort — The curve this one lands on when its pivot rule meets sorted input, and the coincidence is worth seeing drawn.
• Quicksort, partition by partition — One frame per comparison, with the pivot and the two groups marked as the sweep runs. That page shows why a bad pivot is bad; this one shows how much.

All measured subjects