Vieš uviesť algoritmy, ktorých asymptotická zložitosť je lepšia ako u rýchleho triedenia?

Rýchle triedenie v priemere funguje v čase O(n log n), čo je optimálna asymptotika pre porovnávacie algoritmy. Avšak existujú algoritmy s lepšou asymptotickou zložitosťou v niektorých prípadoch:

• Počítacie triedenie (Counting Sort) — O(n + k), kde k je rozsah hodnôt. Funguje rýchlejšie, ak k nie je príliš veľké.
• Radixové triedenie (Radix Sort) — O(d * (n + k)), kde d je počet číslic, k je základ číselného systému. Efektívne pre triedenie čísel alebo reťazcov.
• Zlučovacie triedenie (Merge Sort) — garantovane O(n log n), stabilné a predvídateľné.

Dôležité: algoritmy s lepšou ako O(n log n) zložitosťou nie sú založené na porovnávaní prvkov, ale využívajú dodatočné predpoklady o dátach (napríklad obmedzený rozsah hodnôt).