Countingsort

Countingsort (von englisch count „zählen“) ist ein stabiles Sortierverfahren, das eine gegebene Folge von Elementen mit linearem Zeitaufwand (Problemkomplexität ) sortiert, wenn deren Sortierschlüssel natürliche Zahlen aus einem beschränkten Intervall mit möglichen Werten sind (oder sich darauf abbilden lassen). Der Algorithmus arbeitet nicht vergleichsbasiert, sondern zählt die Vorkommnisse der Schlüsselwerte – er arbeitet dann adressbasiert. Im Vergleich zum vergleichenden Sortieren mit der bestmöglichen Komplexität ergibt sich ein Vorteil, wenn die Intervalllänge sehr klein gegenüber der Anzahl der zu sortierenden Elemente ist. Gut geeignetes Beispiel: Sortieren aller Einwohner Bayerns (n = 12,85 Mio.) nach ihrem Alter (in vollendeten Jahren: k = 0..150). Schlechtes/nicht umsetzbares Beispiel: Sortieren der Schüler einer Grundschule (n = 300) nach ihrem Nachnamen (Zeichenkette mit max. Länge 40 aus allen möglichen Buchstaben, Umlauten und Sonderzeichen; k ≈ 3540).