radixsortering

Radixsortering, eller radixsort, er en ikke-sammenlignende sorteringsalgoritme der sorterer nøgler ved at behandle deres tegn eller cifre i et givet talsystem (radix). I stedet for at sammenligne hele nøgler direkte fordeles elementerne i mindre grupper (bøtter) efter det aktuelle siffer, og processen gentages for hvert siffer. Fordelen er, at algoritmen kan være meget hurtig, især når antallet af signifikante cifre er begrænset.

LSD-sortering (least significant digit) starter ved det mindst signifikante siffer og anvender stabile dele som tælle- eller bucket-sortering for hvert siffer. Efter hvert gennemløb samles elementerne, og processen gentages for det næste siffer. MSD-sortering (most significant digit) starter ved det mest signifikante siffer og deler rekursivt op i sublister, der sorteres separat. Begge tilgange er stabile og udnytter basens struktur.

Når man analyserer tid og plads, afhænger det af n (antal elementer) og k (antal cifre). Generelt giver LSD/MSD en tid på omtrent O(nk) og bruger ekstra plads til bucket- eller tællesortering per pass, typisk O(n + b) per pass, hvor b er radixens størrelse. Det betyder også, at radixsortering ofte ikke er in-place med standardimplementeringer, men kan være in-place i visse varianter.

Radixsortering anvendes især til heltal og faste længde-strenge eller andre nøgler, der kan deles i cifre. Algoritmen er følsom over for fordeling og valg af radix; ved stor radix eller mange cifre kan fordelene mindskes. Det er en stabil sortering, og den kan ofte være konkurrencedygtig i praksis ved større datasæt og en passende base.