Sortieren 2: Mergesort und Quicksort

Eine Million Werte durch Vergleichen jedes Paars zu sortieren, kostet etwa 500 Milliarden Vergleiche; Mergesort braucht etwa 20 Millionen.

Das Problem teilen, die Hälften lösen

Die Verfahren der letzten Einheit arbeiten auf der ganzen Liste auf einmal und bezahlen dafür mit etwa n² Vergleichen. Die beiden Verfahren dieser Einheit folgen einem anderen Plan, genannt Teile und herrsche. Teile die Liste in kleinere Teile, sortiere jeden Teil mit demselben Verfahren und füge dann die sortierten Teile zusammen. Geteilt wird, bis ein Teil einen Wert oder keinen hat, und eine Liste mit einem Wert ist schon sortiert. Weil sich das Verfahren selbst mit kleineren Listen aufruft, ist es rekursiv (Einheit 6 behandelt Rekursion genauer).

Mergesort: Die Arbeit steckt im Zusammenführen

Mergesort schneidet die Liste in zwei Hälften, sortiert die linke Hälfte, sortiert die rechte Hälfte und führt die beiden sortierten Hälften zu einer zusammen. Der Clou ist das Zusammenführen (Mischen). Zwei sortierte Listen lassen sich verbinden, indem man nur auf ihre vorderen Werte schaut. Vergleich die beiden vorderen Werte, schreib den kleineren auf und geh an ihm vorbei. Wiederhol das, bis eine Liste leer ist, und kopier dann den Rest der anderen. Das Zusammenführen von [1, 4, 7] und [2, 3, 8] läuft so: 1 (1 gegen 2), 2 (4 gegen 2), 3 (4 gegen 3), 4 (4 gegen 8), 7 (7 gegen 8), dann wird 8 kopiert: 5 Vergleiche für 6 Werte. Das Zusammenführen zweier Listen mit insgesamt n Werten braucht nie mehr als n − 1 Vergleiche.

function merge(left, right) {
  const out = [];
  let i = 0, j = 0;
  while (i < left.length && j < right.length) {
    if (right[j] < left[i]) out.push(right[j++]);
    else out.push(left[i++]);
  }
  return out.concat(left.slice(i), right.slice(j));
}

function mergeSort(a) {
  if (a.length <= 1) return a;          // schon sortiert
  const mid = Math.floor(a.length / 2);
  return merge(mergeSort(a.slice(0, mid)), mergeSort(a.slice(mid)));
}

Warum ist das schnell? Stell dir das Halbieren als Ebenen vor. Eine Liste mit 8 Werten zerfällt in 2 Listen mit 4, dann in 4 Listen mit 2, dann in 8 Listen mit 1: drei Ebenen, weil man 8 genau 3-mal halbieren kann. Auf jeder Ebene berühren alle Zusammenführungen zusammen jeden Wert einmal, also kostet eine Ebene höchstens etwa n Vergleiche. Bei log₂ n Ebenen sind es insgesamt etwa n log₂ n. Bei einer Million Werten sind das etwa 20 Millionen Vergleiche, gegenüber etwa 500 Milliarden bei den Paar-für-Paar-Verfahren. Geteilt in [38, 27, 43, 3] und [9, 82, 10], wie im Labor, braucht die Liste [38, 27, 43, 3, 9, 82, 10] 14 Vergleiche. Der Code oben teilt sie in 3 und 4 und braucht 13.

Der Preis ist Speicher. Zum Zusammenführen braucht man einen Ort für die Ausgabe, also verwendet Mergesort eine zweite Liste, so groß wie die Eingabe. Mergesort ist außerdem stabil: Werte, die beim Vergleich gleich sind, behalten ihre ursprüngliche Reihenfolge, weil beim Zusammenführen bei gleichen vorderen Werten aus der linken Liste genommen wird. Das zählt, wenn du eine Tabelle nacheinander nach mehreren Spalten sortierst, zum Beispiel nach Stadt und dann nach Name.

Quicksort: um ein Pivot herum aufteilen

Quicksort teilt die Liste auf andere Weise. Es wählt einen Wert, das Pivot (Pivotelement), und ordnet die Liste so um, dass alles, was kleiner als das Pivot ist, davor steht und alles andere dahinter. Diesen Schritt nennt man Partitionieren. Jetzt steht das Pivot an seinem endgültigen Platz, und die beiden Seiten lassen sich mit demselben Verfahren getrennt sortieren. Danach muss nichts zusammengeführt werden, weil jeder Wert links schon kleiner ist als jeder Wert rechts.

Das Labor verwendet eine übliche Lehrbuchversion, die den letzten Wert jedes Teils als Pivot nimmt. Bei [5, 1, 4, 2, 8] wird das Pivot 8 mit den vier anderen Werten verglichen, die alle kleiner sind, also bleibt 8 am Ende. Der nächste Teil [5, 1, 4, 2] nimmt das Pivot 2: Nur 1 ist kleiner, also ist die Liste nach zwei Vertauschungen [1, 2, 4, 5, 8]. Ein weiterer Vergleich erledigt [4, 5]. Insgesamt: 8 Vergleiche und 2 Vertauschungen.

Landet das Pivot nahe der Mitte, halbiert jede Teilung das Problem, und Quicksort braucht wie Mergesort etwa n log₂ n Vergleiche. Es arbeitet außerdem in der ursprünglichen Liste, ohne zweite Kopie. Ein schlechtes Pivot schadet aber. Ist die Liste schon sortiert und das Pivot immer der letzte Wert, löst jede Teilung nur einen einzigen Wert ab, und Quicksort fällt auf etwa n²/2 Vergleiche zurück: 10 bei [1, 2, 3, 4, 5], genauso viele wie Selectionsort. Echte Bibliotheken vermeiden das, indem sie das Pivot sorgfältiger wählen, zum Beispiel zufällig oder als mittleren von drei Stichprobenwerten.