Jak to działa?

Sortowanie przez zliczanie działa w dwóch fazach: zliczanie, a następnie odtwarzanie.

Proces krok po kroku:

1. Zliczanie: utwórz tablicę count, w której count[v] określa, ile razy pojawia się wartość v.
2. Odtwarzanie: przejdź po wartościach od najmniejszej do największej i zapisz każdą wartość v na wyjściu count[v] razy.

Przykład dla [4, 2, 2, 8, 3, 3, 1]:

• Zlicz każdą wartość: 1 pojawia się raz, 2 dwa razy, 3 dwa razy, 4 raz, 8 raz.
• Odtwórz w kolejności: [1, 2, 2, 3, 3, 4, 8].

Nie wykonano żadnych porównań: to sama wartość decydowała, dokąd trafi każdy element.