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

Złożoność czasowa:

• O(n + k)
  • gdzie n to liczba elementów, a k to zakres wartości (maks. + 1). Jedno przejście służy do zliczania, a jedno przejście po zliczeniach do odtworzenia tablicy.
• Gdy k jest małe i stałe, złożoność wynosi w praktyce O(n), co jest szybsze niż O(n log n) w przypadku sortowania przez porównywanie.

Złożoność pamięciowa:

• O(n + k)
  • Tablica zliczeń zajmuje O(k), a wynik O(n).

Podsumowanie:

• Sortowanie przez zliczanie to stabilny algorytm sortowania, który nie korzysta z porównań i działa w czasie liniowym dla małych zakresów liczb całkowitych.
• Nie sprawdza się, gdy zakres wartości k jest bardzo duży, ponieważ tablica zliczeń byłaby ogromna. Ta wersja zakłada nieujemne liczby całkowite.