Normalmente estamos acostumados com algoritmos de ordenação como o MergeSort e QuickSort que funcionam em tempo de execução da ordem de O( lg(n) ) ou até mesmo outros como BubbleSort, Insertion Sort ou Selection Sort, que chegam a tempos de ordenação da ordem de O( n² ). Estes algoritmos são normalmente ensinados nos cursos de graduação. Daí acostumamos com tempos de ordenação grandes e esquecemos que existem algumas situações onde conseguimos tempos de ordenação da ordem de O( n ).
O Counting Sort é utilizado para ordenar vetores de tipos inteiros onde os valores contidos no vetor estão em um intervalo [min, max]. Para ser executado, faz uso de 2 arrays auxiliares, mas com isto consegue um bom tempo de ordenação.
Vamos ver um vídeo com a demonstração deste tipo de ordenação: