Sortowanie przez zliczanie ma jedną dużą zaletę i jedną dużą wadę:
Zaleta: działa w czasie liniowym (jest szybki)
Wada: może sortować wyłącznie liczby całkowite
Obydwie te cechy wynikają ze sposobu sortowania.
Algorytm. Sortowanie to polega na liczeniu, ile razy dana liczba występuje w ciągu, który mamy posortować. Następnie wystarczy utworzyć nowy ciąg, korzystając z danych zebranych wcześniej. Np. mamy posortować ciąg: 3,6,3,2,7,1,7,1. Po zliczeniu (w jednym kroku) operujemy danymi na temat liczności poszczególnych liczb:
Liczba 1 występuje 2 razy
Liczba 2 występuje 1 raz
Liczba 3 występuje 2 razy
Liczba 4 występuje 0 razy
Liczba 5 występuje 0 razy
Liczba 6 występuje 1 raz
Liczba 7 występuje 2 razy
Na podstawie tych danych tworzymy ciąg: 1,1,2,3,3,6,7,7. Jest to ciąg wejściowy, ale posortowany. Należy zauważyć trzy ważne rzeczy:
- Proces zliczania odbył się w jednym kroku
- Nie doszło do ani jednej zamiany elementów
- Proces tworzenia tablicy wynikowej odbył się w jednym kroku
Algorytmy ten posiada jednak również wady: - Do przechowywania liczby wyrazów ciągu musimy użyć tablicy, o liczbie elementów równej największemu elementowi ciągu
- Sortować można jedynie liczby całkowite