Motivation

Counting Sort vergleicht niemals zwei Elemente. Es verwendet deren Werte direkt als Indizes in einem count-Array, was es ermöglicht, in linearer Zeit zu laufen.

Warum Counting Sort lernen?

• Lineare Zeit: es läuft in O(n + k), wobei n die Anzahl der Elemente und k der Wertebereich ist. Wenn k klein ist, schlägt das O(n log n).
• Stabil (bei sorgfältiger Umsetzung): eine Grundlage für Radix Sort, das mehrere Counting-Sort-Durchläufe verkettet.
• Eine andere Idee: Sortieren durch Zählen von Werten anstatt sie zu vergleichen.

Der Kompromiss: es benötigt O(k) Speicher für das count-Array, daher ist es ungeeignet, wenn der Wertebereich riesig ist (zum Beispiel beim Sortieren einer Handvoll Zahlen bis zu einer Milliarde).