Beim allgemeinen Sortieren besteht eine untere Grenze an die Laufzeit von O(n*log(n)). CountingSort kann diese Grenze unterbieten, weil bei CountingSort vorausgesetzt wird, dass die zu sortierenden Objekte innerhalb einer bekannten Grenze sind. Diese Grenze wird ab jetzt k genannt.

k ist somit bekannt, und die zu sortierenden Objekte, die sich im Array befinden, sind im Intervall [0, k] vorzufinden.

CountingSort zählt die Objekte einzeln (dh. es legt ein Array an, was k Elemente hat und zählt die jeweilige Stelle des Arrays hoch, wenn die entsprechende Zahl gefunden wurde). Am Ende dieser Zählrunde haben wir ein Array C mit der Anzahl jedes einzelnen Wertes in unserem Ausgangsfeld. Nun werden die Objekte aus dem Ausgangsfeld durchgegangen und an die richtige Stelle eingefügt, die sich aus den Anzahlen berechnen lässt. Die Positionen werden von hinten berechnet, damit die Sortierung der Elemente untereinander (also welche 1 kam zuerst) nicht verloren geht. Es bietet sich an die Positionen ebenfalls in einem Array zu speichern.

Die Berechnung der Position eines Wertes j erfolgt so: pos(j) = pos(j+1) - c(j+1). Also ist die Position eines Elementes j die Position von j+1 vermindert um die Anzahl des Wertes j+1 im Eingabearray. pos(k) ist dabei immer zuerst die Länge des Eingabefeldes.

Wir sollen folgendes Array sortieren:

Das Feld beinhaltet 10 Elemente, die sich im Intervall [0, 9] befinden (k ist also 9). Ein Zählen der Elemente ergibt für unser Array C:

Zu Beachten ist, dass hier die Indizes von Array bei 0 fangen.

Beim Einfügen der Elemente ist nun wichtig, dass die Positionen eigentlich nur eine Art logischer Zeiger sind, der bei jedem eingefügten Element um eins weiter vor verschoben werden muss (gemeint ist nach links). Außerdem muss das Ausgangsfeld von rechts nach links durchgangen werden um die Reihenfolge unter den einzelnen Werten zu erhalten (damit also die erste sieben vor der zweiten sieben im sortierten Feld erscheint).

Das richtig sortierte Feld in unserem Beispiel sieht wie folgt aus:

Hier eine Beispielimplementierung in der Programmiersprache C:

#include <stdio.h>
 
// um sicherzustellen, dass die Arrays nach der Initialisierung Nullen enthalten
// wird die Funktion init_array benutzt um die Array mit Nullen zu füllen
void init_array(int* feld, int groese)
{
    for (int i=0; i<groese; i++)
    {
        feld[i]=0;
    }
}
 
int main ()
{
    printf("Eingabe Obergrenze (Maximum muss KLEINER ALS Obergrenze sein!):");
    int k=0;
    scanf("%d", &k);
 
    printf ("Anzahl der Werte:");
    int anzahl=0;
    scanf("%d", &anzahl);
 
    // das Eingabefeld wird mit eingegebenen Werten gefüllt
    printf("Eingabe zu sortierendes Array:");
    int feld[anzahl];
    init_array(feld, anzahl);
    for (int i=0; i<anzahl; i++)
    {
        scanf("%d", &feld[i]);
    }
 
    // die Werte des Feldes werden gezählt
    int c[k];
    init_array(c, k);
    for (int j=0; j<anzahl; j++)
    {
        c[feld[j]]++;
    }
 
    // aus den Anzahlen lassen sich die Positionen der Elemente im sortierten Feld
    // wie folgt berechnen: pos(j)=pos(j+1) - c(j+1)
    // also: Die Position einer Zahl j ist die Position der Zahl j+1 um die Anzahl
    // von j im Eingabearray vermindert.
    int pos[k];
    init_array(pos, k);
    pos[k-1]=anzahl-1;
    for (int j=k-2; j>=0; j--)
    {
        pos[j]=pos[(j+1)]-c[(j+1)];
    }
 
    // Hier wird das Array mit den sortieren Werten gefüllt
    // die Position von j wird grundsätzlich um 1 vermindert, wenn man ein Element
    // j eingefügt hat
    int sortiert[anzahl];
    init_array(sortiert, anzahl);
    for (int j=anzahl-1; j>=0; j--)
    {
        sortiert[pos[feld[j]]]=feld[j];
        pos[feld[j]]--;
    }
 
    for (int j=0; j<anzahl; j++)
    {
        printf (" %d ", sortiert[j]);
    }
    printf ("\n");
    return 0;
}