Motywacja

Sortowanie przez zliczanie nigdy nie porównuje dwóch elementów. Wykorzystuje ich wartości bezpośrednio jako indeksy w tablicy count, dzięki czemu działa w czasie liniowym.

Dlaczego warto poznać sortowanie przez zliczanie?

• Czas liniowy: działa w O(n + k), gdzie n to liczba elementów, a k to zakres wartości. Gdy k jest małe, jest szybsze niż O(n log n).
• Stabilność (przy starannym wykonaniu): stanowi podstawę sortowania Radix, które łączy kilka przebiegów sortowania przez zliczanie.
• Inny pomysł: sortowanie przez zliczanie wystąpień wartości zamiast ich porównywania.

Kompromis polega na tym, że potrzebuje O(k) pamięci na tablicę zliczającą, więc słabo się sprawdza, gdy zakres wartości jest ogromny (na przykład przy sortowaniu garści liczb o wartości do miliarda).