Aká je vlastne zložitosť takéhoto triedenia? Vidíme, že rozdeliť pole podľa pivota $p$ -- zpivotizovať ho nám trvá čas $O(n)$. A ak by sme si vybrali prvok $p$ vždy tak, aby menšie prvky tvorili polovicu všetkých prvkov, mali by sme $\log n$ úrovní, na každej s prácou $O(n)$, takže výsledný čas by bol $O(n \log n)$.
To je síce pekné, ale príliš optimistické. Poďme sa pozrieť aj na to, ako najdlhšie môže bežať náš algoritmus. Môžeme mať smolu a prvok $p$ si vždy vybrať ako najväčší prvok nášho neutriedeného poľa. To znamená, že namiesto $\log n$ úrovní, budeme mať úrovní $n$. A na každej bude stále o jedna menej prvkov. To znamená, že zložitosť bude $O(n^2)$. To ako vieme, je pre veľké polia nepoužiteľné. Čo s tým?
Ak by sme chceli, aby náš program rozdelil pole vždy na polovice, ako prvok $p$ by sme si museli zvoliť stredný prvok postupnosti -- medián. Pozitívne je, že existuje algoritmus, ktorý nájde medián v postupnosti v čase $O(n)$. Bohužiaľ, tento algoritmus je dosť komplikovaný a má privysokú konštantu, aby sa dal používať prakticky. To, čo teda spravíme je, že to necháme na náhodu.
Pozrime sa na to tak intuitívne. Ak vyberiem daný prvok z ešte neutriedených prvkov, náhodne, je predsa oveľa pravdepodobnejšie, že to bude prvok blízko stredu ako to, že to bude prvok maximálny. Existuje dôkaz (bohužiaľ trochu komplikovanejší), ktorý ukáže, že v priemernom prípade je časová zložitosť quick sortu naozaj $O(n \log n)$ a je veľmi nepravdepodobné, že to bude viac. A to naozaj úplne stačí. Dostaneme jednoduchý a rýchly algoritmus.