Konstanta vyhrává na malých datech

Tohle je statická kopie kapitoly pro vyhledávače. Interaktivní verze má animované obrázky, kontrolní otázky a tlačítka, která příklad načtou do kalkulačky.

Tohle je ta část, kterou O() zahodilo — a ukáže se, že je v praxi rozhodující častěji, než by člověk čekal, protože většina polí, která se v reálném kódu třídí, je malá.

Táhni počtem prvků a sleduj obě křivky. Vlevo od svislé červené čáry vyhrává „pomalejší“ kvadratický algoritmus — a není to blízko, je to výrazně.

Třídění vkládáním má malou konstantu: vnitřní smyčka je porovnání a posun, nic víc, žádná rekurze, žádná alokace, a data jsou v paměti hned vedle sebe. Slučování má velkou konstantu: volání funkcí, alokace, kopírování tam a zpátky.

vkládáním ≈ 0,5·n² vs slučováním ≈ 6·n·log₂nty konstanty jsou to, co rozhoduje

Průsečík vychází kolem n = 12 pro tenhle konkrétní pár implementací. Přesná hodnota závisí na jazyce, procesoru a datech — proto se v knihovnách ta hranice ladí měřením a bývá mezi 8 a 32.

Proto skutečné knihovní třídění není jeden algoritmus. Timsort (Python, Java pro objekty) i introsort (C++) i pdqsort (Rust, Go) dělají totéž: jedou rozděl-a-panuj, a jakmile podúloha klesne pod pár desítek prvků, dotřídí ji vkládáním. Není to kompromis — je to využití obou konců té křivky.

A ještě jeden důvod, proč se malé případy vyplatí řešit zvlášť

Rekurze má vlastní cenu: každé zanoření je zápis na zásobník. Pro pole o třech prvcích je ta režie větší než samotná práce. Ukončit rekurzi dřív a dodělat to přímočaře je proto úspora na obou stranách — méně volání i lepší chování cache (kapitola 10).

Co si z toho odnést obecně

Než se optimalizuje složitost, je dobré vědět, jak velké to n vlastně je. Přepsat kvadratický algoritmus na n log n je smysluplné pro n v tisících. Pro n = 10 je to práce navíc, která výsledek zpomalí — a stálo by to za to změřit, protože v tomhle oboru je intuice mimořádně nespolehlivá.