5.7. Számjegyes (radix) rendezés

Ha a kulcsok összetettek, több komponensekből állnak, akkor rendezhetünk az egyes komponensek szerint. Például a dátum az év, hónap, nap rendezett hármasából áll. Ha a kulcsok utolsó komponense szerint rendezünk, majd az eredményt az utolsó előtti komponens szerint, és így tovább, akkor végül rendezett sorozathoz jutunk.

Az egész számok tekinthetőek bitsorozatoknak, s a rendezés minden egyes fordulójában két sorozattá bontjuk a kiinduló, illetve az eredményül kapott sorozatokat, aszerint, hogy a vizsgált bit 0 illetve 1. E két lista egymás után fűzéséből kapható meg a soron következő sorozat. (Természetesen nemcsak kettes, hanem bármilyen más számrendszerbeli számokként is tekinthetnénk a sorozat elemeit, s például négyes számrendszer esetén négy sorozattá bontatánk a sorozatot.) Kettes számrendszer használata esetén, ha a számok 0 és 2k − 1 közé esnek, akkor a bonyolultság O(nk).

5.4. példa - 7. példa

Legyenek a számaink

4 9 13 15 5 2 10 7 1 8

Ezek kettes számrendszerben a következőek:

0100 1001 1101 1111 0101 0010 1010 0111 0001 1000

Az utolsó bit szerint szétválasztva az előbbi listát a következőt kapjuk:

0100 0010 1010 1000 1001 1101 1111 0101 0111 0001

A harmadik bit szerint

0100 1000 1001 1101 0101 0001 0010 1010 1111 0111

A második bit szerint

1000 1001 0001 0010 1010 0100 1101 0101 1111 0111

S végül az első bit szerint rendezve

0001 0010 0100 0101 0111 1000 1001 1010 1101 1111

Amelyek tízes számrendszerben

1 2 4 5 7 8 9 10 13 15

tehát valóban rendeztük a sorozatot.