spezielles Sortierverfahren zum Sortieren von n ganzen Zahlen eines Bereiches [1 … k] für eine feste natürliche Zahl k.

Das Verfahren besteht aus drei Schritten. Im ersten Schritt wird für jedes i ∈ {1, …, k} gezählt, wieviele Elemente der Eingabefolge, die in einem Feld A[1 … n] der Größe n abgespeichert ist, den Schlüssel i haben. Dieses Zwischenergebnis wird in einem Feld C der Größe k abgespeichert. Die Komponente C[i] speichere die Anzahl der Elemente der Eingabefolge mit dem Schlüssel i.

Im zweiten Schritt wird für alle i ∈ {1, …, k} die Anzahl der Elemente der Eingabefolge, die einen Schlüssel kleiner gleich i haben, berechnet. Dies erfolgt sequentiell, beginnend mit i = 2 bis hin zu i = n durch Setzen der iten Komponente C[i] von C auf C[i] + C[i – 1].

Im dritten Schritt wird die Eingabefolge (beginnend mit dem letzten Element A[n] der Eingabefolge) durch direktes Einreihen in ein Feld B[1 … n] der Größe n sortiert. Dies erfolgt jeweils durch die Befehlssequenz

\begin{eqnarray}\begin{array}{c}\text{B[C[A[j]]]:=A[j];}\\ \text{C[A[j]]:=C[A[j]]-1}\text{.}\end{array}\end{eqnarray}

Countingsort ist ein stabiles Sortierverfahren. Es benötigt höchstens c₁ · n + c₂ · k Schritte, um eine Eingabefolge der Länge n zu sortieren. Hierbei bezeichnen c₁ und c₂ zwei von n und k unabhängige Konstanten.