Complessità temporale e spaziale

Complessità temporale:

• O(n + k)
  • dove n è il numero di elementi e k è l'intervallo dei valori (max + 1). Un passaggio per contare, un passaggio sui conteggi per ricostruire.
• Quando k è piccolo e fisso, è di fatto O(n), più veloce di O(n log n) degli algoritmi di ordinamento per confronto.

Complessità spaziale:

• O(n + k)
  • L'array dei conteggi usa O(k) e l'output usa O(n).

Riepilogo:

• Counting Sort è un algoritmo di ordinamento stabile e non basato sul confronto, che opera in tempo lineare per intervalli di interi piccoli.
• È poco adatto quando l'intervallo dei valori k è molto ampio, perché l'array dei conteggi sarebbe enorme. Questa versione presuppone interi non negativi.