Motywacja

Radix Sort nigdy nie porównuje bezpośrednio dwóch liczb. Grupuje je według kolejnych cyfr, używając stabilnego sortowania pomocniczego, dzięki czemu może przekroczyć barierę O(n log n), której nie mogą pokonać algorytmy sortujące przez porównania.

Dlaczego warto poznać Radix Sort?

• Prawie liniowy czas: działa w czasie O(d * (n + k)), gdzie d to liczba cyfr, a k to podstawa systemu liczbowego (tutaj 10). W przypadku liczb o ograniczonej liczbie cyfr jest to w praktyce O(n).
• Stabilność: równe wartości zachowują swoją kolejność względną, co umożliwia prawidłowe łączenie przebiegów sortowania według kolejnych cyfr.
• Inny pomysł: pokazuje, że sortowanie nie musi polegać na porównywaniu — to ważna koncepcja w przypadku dużych liczb całkowitych lub kluczy o stałej długości.

Kompromis: potrzebuje kluczy, które można rozłożyć na cyfry (tutaj są to nieujemne liczby całkowite), oraz dodatkowej pamięci na kubełki.