Loppuosataulukon muodostus

Lajittelu suoritetaan $\lceil \log_2(N+1) \rceil$ vaiheessa. Loppuosat lajitellaan ensin lokeroihin osituslajittelulla (radix sort) ensimmäisen symbolin mukaan. Tämän jälkeen jokaisessa vaiheessa lajitellaan aikaisemman vaiheen lokeroiden sisällöt uusin lokeroihin siten, että jokaisessa vaiheessa lajittelun perusteena käytetään kaksi kertaa niin pitkää alkuosaa kuin edellisessä vaiheessa.

Merkitään lajittelun vaihetta ja lajittelukriteerinä käytettävän alkuosan pituutta $H$:lla siten, että $H=1,2,4,8, \dots$ lajittelun edetessä. Olkoon $S_i$ ja $S_j$ kaksi loppuosaa, jotka kuuluvat samaan lokeroon jossain lajittelun vaiheessa. Tällöin $S_i$:llä ja $S_j$:llä on ainakin $H$ symbolia pitkä yhteinen alkuosa. Ongelmaksi jää $S_i$:n ja $S_j$:n välinen vertailu seuraavien $H$:n symbolin mukaan. Kuitenkin tämä vertailu on jo suoritettu, koska $S_{i+H}$ ja $S_{j+H}$ on jo lajiteltu lokeroihin ensimmäisten $H$ symbolin perusteella.

Olkoon $S_i$ ensimmäinen loppuosa ensimmäisessä lokerossa (lokerossa, jonka $H$-alkuosat ovat ensimmäisenä aakkosjärjestyksessä). Koska $S_i$:n ensimmäiset $H$ symbolia sisältävä osajono on aakkosjärjestyksessä pienin kaikista $H$ symbolin mittaisista symbolijonoista, loppuosan $S_{i-H}$ täytyy olla ensimmäisenä sen omassa $2H$:n pituisten alkuosien mukaan järjestetyssä lokerossa. Tämän ansiosta $S_{i-H}$ siirretään ensimmäiseksi sen omassa lokerossa ja siirto merkitään tehdyksi. Jokaista lokeroa kohden täytyy säilyttää tietoa jo siirrettyjen (ja siten myös järjestettyjen) loppuosien lukumäärästä. Algoritmi käy järjestyksessä läpi kaikki $H$:n symbolin mukaan järjestetyt loppuosat $S_i$ ja siirtää jokaisen loppuosan $S_{i-H}$ omassa lokerossaan seuraavalle vapaalle paikalle. Kun kaikki loppuosat on käyty läpi tasolla $H$, siirrytään tasolle $2H$. Yhden tason läpikäynnin aikavaatimus on $O(n)$. Koska tasoja on enintään $\lceil \log_2(n+1) \rceil$, lajittelun kokonaisaikavaatimus on $O(n \log n)$ pahimmassa tapauksesa.