Rozděl a panuj: odkud se bere to log n
Kvadratická třídění srovnávají každý prvek skoro s každým. Rychlá třídění dělají něco jiného: rozdělí úlohu na dvě poloviny, vyřeší je zvlášť a výsledky spojí — a to spojení je levné.
Kde se vezme ten logaritmus
Pole o velikosti n se dá půlit log₂ n krát, než zbudou jednotlivé prvky. Na každé úrovni toho půlení se udělá dohromady n práce (každý prvek se dotkne právě jednou), a úrovní je log₂ n:
Pro n = 1 000 000 je log₂ n asi 20. Kvadratický algoritmus by udělal 5·10¹¹ operací, ten n log n asi 2·10⁷ — rozdíl je faktor 25 000, a to je ten skok, kvůli kterému se ta složitost učí.
Slučování: cena, kterou porovnání neukážou
Sloučit dvě setříděné poloviny je snadné — porovnávají se jejich čela. Jenže výsledek se musí někam zapsat, a to znamená alokovat pole o velikosti n. Je to jediný běžný třídicí algoritmus, který si žádá paměť navíc.
| slučováním | quicksort | |
|---|---|---|
| nejhorší případ | n log n vždycky | n² |
| paměť navíc | n | žádná (jen zásobník) |
| stabilní | ano | ne |
| hloubka rekurze | log n | log n až n |
Ta tabulka je celý důvod, proč existují oba. Slučování se používá tam, kde je potřeba záruka (Java pro objekty, protože stabilita je součást specifikace), quicksort tam, kde je paměť pevná a průměr stačí.
V regulační smyčce je alokace problém sama o sobě, i kdyby byla rychlá — protože doba jejího trvání není předvídatelná. Kapitola 11 to rozvádí; zatím stačí, že „n log n“ a „vejde se do smyčky“ jsou dvě nezávislé vlastnosti.