Il counting sort ha complessità lineare rispetto alla lunghezza N del vettore da ordinare se il numero di elementi tra il minimo e il massimo del vettore è lineare in N. Esempio: devi ordinare un vettore di 100 interi; se tali interi variano tra 0 e 100 il counting sort effettuerà k*100 operazioni; se gli elementi variano tra 0 e 1000.000 il counting sort effettuerà k*1000.000 di operazioni...nella pratica sono rari i casi in cui puo essere aplicato.