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).
Algorithmus
Countingsort setzt voraus, dass die zu sortierenden Schlüsselwerte der Eingabe in einem beschränkten Intervall 
liegen (oder sich einfach darauf abbilden lassen). Der Algorithmus zählt, wie oft jeder dieser Werte in der Eingabe vorkommt. Diese Anzahlen speichert er in einem zusätzlichen Array mit Feldern ab. Mit Hilfe dieses Arrays wird anschließend für jeden Schlüsselwert die Zielposition in der Ausgabe berechnet.
Eingabe:
Array ![{\displaystyle A[1..n]}](https://wikimedia.org/api/rest_v1/media/math/render/svg/77350b7b7a24749675609a440314e0ab8aded3d5)
mit ![{\displaystyle A[j]\in \{0,\ldots ,(k-1)\}}](https://wikimedia.org/api/rest_v1/media/math/render/svg/63123c97cec34d9509af09e8e60d8e577816b788)
für alle 
und die rechte Intervallgrenze 
.
Ausgabe:
Feld ![{\displaystyle B[1..n]}](https://wikimedia.org/api/rest_v1/media/math/render/svg/7bc6aa2e55a7d9ee100e0605dd87ff62a401dea0)
mit Inhalt von 
in sortierter Reihenfolge.
Zusätzlicher Speicher: Während der Sortierung benötigt der Algorithmus ein Hilfs-Array ![{\displaystyle C[0..(k-1)]}](https://wikimedia.org/api/rest_v1/media/math/render/svg/a4f0f5ac6a9a020a6e5bbb30e480974ce34b0080)
.
Angabe des Algorithmus in Pseudocode:
countingsort(A,k)
{
C = array(0,k-1)
// Initialisiere das Array C mit Nullen
for (m=0; m<k; m++)
C[m] = 0
// end for
// Schreibe in C[m], wie häufig der Wert m in A vorkommt
for (j=1; j<=A.size; j++)
C[key(A[j])] += 1
// end for
// Adressrechnung
for (m=1; m<k; m++)
C[m] += C[m-1]
// end for
B = array(1, A.size)
// Kopiere auf jeweilige Zieladresse in B (mit Dekrementierung)
for (j=A.size; j>0; j--) {
B[ C[ key(A[j]) ] ] = A[j]
C[key(A[j])] -= 1
}
return B
}
Die Funktion key gibt den Sortierschlüssel des Array-Elements der Eingabe zurück. Wenn ein Array-Element nur aus dem Sortierschlüssel besteht und keine weitere Komponenten enthält, dann ist 
.
In der ersten for-Schleife wird das Hilfs-Array 
initialisiert.
Die zweite for-Schleife iteriert über die Eingabe und inkrementiert für jeden Sortierschlüssel das zugeordnete Array-Element Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle C[\text{key}(A[j])]}
. Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle C[m]}
enthält somit die Anzahl, wie oft der Schlüsselwert Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle m}
in Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle A}
vorkommt.
In der dritten for-Schleife werden die Zähler in Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle C}
akkumuliert, so dass nach dem Ende der Schleife Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle C[x]}
die letzte Position für ein Element mit Schlüsselwert Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle x}
im Ausgabe-Array bezeichnet. Somit enthält Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle C[m]}
jetzt nicht mehr „Anzahl der ‚m-Elemente‘ in A“, sondern die „Adresse des ‚m-Abschnitts‘ für B“ (allerdings die Endadresse, nicht die Startadresse).
Die letzte for-Schleife durchläuft die Eingabe von rechts nach links (aufgrund der Endadressen in Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle C}
), und sortiert den jeweiligen Eintrag dabei ein:
Ist die Schleife in Iteration Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle j}
, so hat Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle A[j]}
den Schlüsselwert Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle m_j}
(= Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle \text{key}(A[j])}
). Dieser muss also einsortiert werden an Adresse Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle C[m_j]}
. Anschließend wird die Zieladresse Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle C[m_j]}
dekrementiert, damit das nächste Element in Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle A}
, welches den Schlüssel Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle m_j}
besitzt, eine Position weiter vorne einsortiert wird.
Durch die sprungfreie Iteration wird die relative Reihenfolge von mehreren Elementen der Eingabe mit dem gleichen Sortierschlüssel auch in der Ausgabe nicht verändert, d. h. Countingsort sortiert stabil.
Vereinfachter Algorithmus
Wenn die Eingabe ein einfaches Zahlen-Array ist, dann kann Countingsort ohne eine Akkumulationsphase dargestellt werden:
countingsort(A, k)
{
C = array(0, (k-1))
for (m=0; m<k; m=m+1)
C[m] = 0
// end for
for (j=1; j<=A.size; j=j+1)
C[A[j]] = C[A[j]] + 1
// end for
i=0
B = array(1, A.size)
for (m=0; m<k; m=m+1) {
while (C[m]>0) {
B[i] = m
C[m] = C[m]-1
i = i+1
}
}
return B
}
Hierbei wird ausgenutzt, dass es dann nicht notwendig ist, die Inhalte von A nach B zu kopieren – es genügt, die Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle m}
-Abschnitte von B mit so vielen Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle m}
-Ganzzahlen zu füllen, wie im jeweiligen Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle C[m]}
vermerkt ist.
Funktionsbeispiel
Ausführung von Countingsort auf ein Eingabefeld Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle A[1 .. 8]}
mit Elementen aus Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle \{0, \ldots, 5\}}
mit Hilfsfeld Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle C}
und sortierter Ausgabe in Feld Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle B}
.
| 1
|
2
|
3
|
4
|
5
|
6
|
7
|
8
|
| 2
|
5
|
3
|
0
|
2
|
3
|
0
|
3
|
Darstellung untereinander: Ausgangsarray Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle A}
, Hilfsarray Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle C}
, dessen Länge vom Definitionsbereich des Arrays abhängt. In das unterste Array werden die Elemente sortiert eingefügt.
Die obige Abbildung stellt die gegebene Zahlenfolge dar, wobei die erste Schleife des Algorithmus bereits abgearbeitet wurde, indem lediglich das Array Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle C}
mit 0 initialisiert wird. Die zweite Schleife inkrementiert für jede Ziffer deren Stelle im Array um eins.
| 1
|
2
|
3
|
4
|
5
|
6
|
7
|
8
|
| 2
|
5
|
3
|
0
|
2
|
3
|
0
|
3
|
Die dritte Schleife summiert das Array Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle C}
auf, so dass dessen Inhalt angibt, bis zu welcher Position ein Wert in dem sortierten Array auftaucht. Zwei gleiche aufeinanderfolgende Zahlen bedeuten dabei, dass die letzte der beiden Zahlen in der Folge überhaupt nicht auftaucht, also vorher in Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle C}
an dieser Position ein 0 gewesen war.
In Array Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle C}
stehen nun also statt der Anzahlen, wie oft ein Wert im Array A enthalten ist, stattdessen Endadressen (bzw. End-Indizes):
- Der letzte Wert '5' aus Array A muss an Index 8 in das Zielarray B;
- der Wert '4' kam in Array A nicht vor und hat daher dieselbe Endadresse wie der Wert '3';
- die letzte '3' aus Array A muss an Index 7 in das Zielarray B – anschließend wird die Zieladresse C['3'] um 1 heruntergezählt, so dass die nächste '3' aus Array A den Zielindex 6 erhält und somit nach B[6] kopiert wird;
- die letzte '2' aus Array A muss an Index 4 (also B[4]), weitere '2'er aus A müssen vor Index 4;
- '1' kommt in A nicht vor, daher hat es dieselbe „letzte Zieladresse“ wie der Wert '0';
- die letzte '0' aus Array A hat die Zieladresse C['0'], also 2. Sobald sie in das Array B einsortiert wurde (also nach B[2]), muss C['0'] um 1 heruntergezählt werden, damit die nächste '0', die in Array A gefunden wird, nach Index C['0']=1, also in das Feld B[1] kopiert wird.
| 1
|
2
|
3
|
4
|
5
|
6
|
7
|
8
|
| 2
|
5
|
3
|
0
|
2
|
3
|
0
|
3
|
In der letzten Schleife werden sukzessive die Werte aus Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle A}
in das Array Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle B}
übertragen und zwar genau an der Stelle im Zielarray, die das Hilfsarray Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle C}
für die entsprechende Zahl angibt. Vor der Schleife ist dies immer die letzte Stelle, an der die Zahl auftauchen wird. Nach dem Übertragen jeder Zahl wird zusätzlich der Wert in Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle C[Zahl]}
dekrementiert. Die nächste gleiche Zahl wird deswegen eine Stelle weiter vorne im Zielarray eingefügt. Nachfolgend die 8 Schritte.
Die ersten 7 Schritte im Detail
1. Schritt
| 1
|
2
|
3
|
4
|
5
|
6
|
7
|
8
|
| 2
|
5
|
3
|
0
|
2
|
3
|
0
|
3
|
2. Schritt
| 1
|
2
|
3
|
4
|
5
|
6
|
7
|
8
|
| 2
|
5
|
3
|
0
|
2
|
3
|
0
|
3
|
3. Schritt
| 1
|
2
|
3
|
4
|
5
|
6
|
7
|
8
|
| 2
|
5
|
3
|
0
|
2
|
3
|
0
|
3
|
4. Schritt
| 1
|
2
|
3
|
4
|
5
|
6
|
7
|
8
|
| 2
|
5
|
3
|
0
|
2
|
3
|
0
|
3
|
5. Schritt
| 1
|
2
|
3
|
4
|
5
|
6
|
7
|
8
|
| 2
|
5
|
3
|
0
|
2
|
3
|
0
|
3
|
| 1
|
2
|
3
|
4
|
5
|
6
|
7
|
8
|
| 0
|
0
|
|
2
|
|
3
|
3
|
|
6. Schritt
| 1
|
2
|
3
|
4
|
5
|
6
|
7
|
8
|
| 2
|
5
|
3
|
0
|
2
|
3
|
0
|
3
|
| 1
|
2
|
3
|
4
|
5
|
6
|
7
|
8
|
| 0
|
0
|
|
2
|
3
|
3
|
3
|
|
7. Schritt
| 1
|
2
|
3
|
4
|
5
|
6
|
7
|
8
|
| 2
|
5
|
3
|
0
|
2
|
3
|
0
|
3
|
| 1
|
2
|
3
|
4
|
5
|
6
|
7
|
8
|
| 0
|
0
|
|
2
|
3
|
3
|
3
|
5
|
8. Schritt
| 1
|
2
|
3
|
4
|
5
|
6
|
7
|
8
|
| 2
|
5
|
3
|
0
|
2
|
3
|
0
|
3
|
| 1
|
2
|
3
|
4
|
5
|
6
|
7
|
8
|
| 0
|
0
|
2
|
2
|
3
|
3
|
3
|
5
|
Komplexität
Laufzeitanalyse
Die Laufzeit der Funktion hängt von Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle n}
(Anzahl der Elemente des Eingabearrays) und Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle k}
(die Größe des Zahlenintervalls) ab. Die for-Schleifen werden jeweils Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle n}
-mal oder Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle k}
-mal durchlaufen. Die Zeitkomplexität von Countingsort beträgt somit Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle \mathcal{O}(n + k)}
.
Speicherplatzbedarf
Zusätzlich zur Ein- und Ausgabe, die jeweils Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle n}
Speicherfelder benötigen (out-of-place), wird noch ein temporäres Array zur Speicherung der Häufigkeiten der Zahlenwerte angelegt. Dieses benötigt Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle k}
Elemente Speicherplatz. Die Platzkomplexität von Countingsort liegt also in Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle \mathcal{O}(n + k)}
.
Literatur
- Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest, Clifford Stein: Introduction to Algorithms. 2. Auflage. MIT Press, Cambridge MA 2001, ISBN 0-262-03293-7, S. 168–170.
- Donald E. Knuth: The Art of Computer Programming: Volume 3 Sorting and Searching. 2. Auflage. Addison-Wesley, Reading MA 1997, ISBN 0-201-89685-0, S. 78.
- W. Feurzeig: Algorithm 23: Math Sort. In: Communications of the ACM. Band 3, Nr. 11, 1960, S. 601.
- H. H. Seward: M.I.T. Digital Computer Laboratory Report R-232. 1954, S. 25–28 (Masterarbeit).
Weblinks
