Řadicí algoritmus: Porovnání verzí

Pro seřazení množiny <math>n</math> prvků existuje očividná dolní mez časové [[asymptotická složitost|asymptotické složitosti]][2] <math>\Omega(n)</math> (každý prvek je potřeba alespoň jednou přečíst). Této dolní meze je ale možno dosáhnout jen při předem známé, omezené množině klíčů (např. [[interval (matematika)|interval]] v [[přirozené číslo|přirozených číslech]]). Lze dokázat, že u řazení, které je založeno na porovnávání dvojic klíčů (což je univerzální metoda použitelná pro libovolná data), je minimální časová složitost <math>\Omega(n \log n)</math>.