Złożoność czasowa i pamięciowa

Złożoność czasowa:

• O(d * (n + k))
  • gdzie n to liczba elementów, k to podstawa (10), a d to liczba cyfr w największej wartości. Każde z d przejść wykonuje O(n + k) operacji.
• Gdy d jest małe i stałe, algorytm działa jak O(n), szybciej niż sortowania porównawcze o złożoności O(n log n).

Złożoność pamięciowa:

• O(n + k)
  • Każde przejście tworzy tablicę wynikową o rozmiarze n oraz tablicę zliczeń o rozmiarze k.

Podsumowanie:

• Radix Sort to stabilne sortowanie nieporównawcze, które może być szybsze niż O(n log n) dla kluczy całkowitych o ograniczonej liczbie cyfr.
• Wymaga kluczy, które można rozdzielić na cyfry, oraz dodatkowej pamięci; ta wersja zakłada nieujemne liczby całkowite.