5.5. Lineáris idejű rendezések

A beszúró, az összefésülő, a gyors- és a kupacrendezésnél azt használtuk fel, hogy a sorozat két eleme között milyen reláció áll fenn. Könnyen belátható, hogy vizsgálatainkat leszűkíthetjük egyedül a kisebb-egyenlő vizsgálatára. Ezt az egy relációt használva döntési fákat készíthetünk, melyben ha a fa adott csúcsában szereplő kérdésre igaz a válasz, akkor a csúcs bal fiánál folytatjuk a vizsgálódást, különben a jobb fiánál. Ha elértünk egy levélhez, akkor az ott szereplő lista az elemek rendezését adja meg. Három elem esetén a következő ábra tartalmazza a döntési fát:

Miután az n elem összes permutációjának szerepelnie kell a döntési fa leveleiben, ebből az következik, hogy a döntési fa magassága n ln(n)-nel lesz arányos, ha a döntési fa optimális felépítésű. Azaz legalább n ln(n) összehasonlítást kell elvégezni n elem rendezéséhez. Magyarul az optimális lépésszám n ln(n)-nel arányos, ennél jobb bonyolultságú rendezés általános esetben nem létezik. Tehát a kupacrendezés és az összefésülés optimális rendezési módszer.