Skatteregistret
Eftersom N=223 tar quicksort 9 000 000*23= 207 miljoner jämförelser.
Radixsortering är snabbare!
- Räkna ut längden av det längsta talet, k
- Använd räknesortering för att sortera efter sista siffan i talet
- Använd sedan räknesortering för att sortera efter näst sista siffan i talet
- ... gör på samma sätt för alla siffror, dvs k varv
Här måste vi alltså gå igenom alla personnummer, dela upp i tio buntar efter sista siffran, lägg samman, gör om med näst sista siffran etc , tills alla siffror är genomgångna.
Detta tar tar 10*9000000= 90 miljoner jämförelser. Man kan faktiskt strunta i sista siffran eftersom den är checksiffra. Det finns inte två pnr som bara skiljer sej i den siffran.
Räknesortering är en stabil sorteringsmetod.