P-5.3 Sorting

What this is and why it exists

Sorting is the standard vehicle for teaching algorithm design. Every technique shows up in it, and the analysis is unusually clean.

Three results are worth carrying away. Comparison sorting cannot beat a linear-logarithmic bound. Quicksort's famous speed comes with a quadratic worst case. And stability is a real property with real consequences.

That last one catches people in production rather than in exams, which is why it gets a section of its own.

The vocabulary

• Comparison sort — a sort whose only tool is comparing two items.
• In place — sorting without significant extra memory.
• Pivot — the value quicksort partitions around.
• Partition — rearranging so smaller items sit on one side of the pivot.
• Merge — combining two sorted sequences into one.
• Stable — equal items keep their original relative order.
• Lower bound — a limit that applies to every algorithm of a kind, not one.

The mental model

Start with the quadratic sorts, and write one once. Selection, insertion and bubble sort are slow on large inputs and genuinely competitive on small ones. That is not a consolation prize: real libraries fall back to insertion sort below a threshold, for exactly this reason.

Merge sort divides, sorts each half, and merges. The recursion splits until sorting is trivial, and the actual work happens on the way back up. Its most valuable property is that its cost is the same on every input. There is no bad case to worry about, which is precisely what quicksort lacks.

Quicksort chooses a pivot and partitions around it. It sorts in place and it is very fast in practice, which is why it is everywhere. But a consistently bad pivot degrades it to quadratic. This is why real implementations randomise or sample the pivot rather than taking the first element. The randomisation defends against unlucky and against hostile input.

Then the lower bound, which is a different kind of result and worth following once. There are more possible orderings of n items than a shorter sequence of yes-or-no comparisons can distinguish between. Count both sides and the bound falls out. What makes it worth your time is that it is a proof about every comparison sort, including ones nobody has invented. Most results are about one algorithm; this one is about a whole class.

Finally stability. A stable sort leaves equal items in their original relative order. That is what lets you sort by name, then sort by department, and end up with departments in order and names in order within each. An unstable sort silently discards the first ordering. Nothing reports it, the output looks sorted, and it is wrong in a way people notice weeks later.

What you should now be able to explain or do

Implement merge sort and quicksort. Say why the quadratic sorts still appear inside real libraries. State which sort has the same cost on every input and why that matters. Explain quicksort's worst case and why implementations randomise the pivot. Follow the counting argument behind the comparison lower bound. Define stability and give the two-field example where it decides correctness.

Check yourself