Motivazione

Counting Sort non confronta mai due elementi. Usa direttamente i loro valori come indici in un array di conteggio, ed è questo che gli permette di funzionare in tempo lineare.

Perché imparare Counting Sort?

• Tempo lineare: funziona in O(n + k), dove n è il numero di elementi e k è l’intervallo dei valori. Quando k è piccolo, è più efficiente di O(n log n).
• Stabile (se eseguito con attenzione): è alla base di Radix Sort, che concatena diverse passate di counting sort.
• Un’idea diversa: ordinare contando i valori invece di confrontarli.

Il compromesso: richiede O(k) memoria per l’array di conteggio, quindi è poco adatto quando l’intervallo dei valori è enorme (per esempio, per ordinare una manciata di numeri fino a un miliardo).