Mergesort und „Teile und herrsche“ in JavaScript

Problem

„Nach Preis sortieren“ bei 100.000 Produkten

Der Onlineshop ist auf 100.000 Produkte gewachsen. Der Knopf „Nach Preis sortieren“ benutzt Insertionsort aus den einfachen Sortierverfahren.

Bei 1000 Produkten macht Insertionsort 256.555 Vergleiche, und die Seite öffnet sich sofort. Bei 100.000 sind es etwa 2,5 Milliarden Vergleiche. Die Produkte sind 100-mal mehr, und die Arbeit ist 10.000-mal größer: Insertionsort ist O(n²), weil jeder neue Preis mit allen Preisen davor verglichen werden kann.

Du brauchst einen Weg, bei dem doppelt so viele Produkte etwas mehr als doppelt so viel Arbeit ergeben.

Die Idee

Teile und herrsche

Wie sortieren zwei Personen einen Stapel von 1000 Rechnungen nach Betrag? Sie teilen ihn in zwei, jede sortiert ihre Hälfte, dann fügen sie zusammen: Sie schauen auf die oberste Rechnung beider Stapel und nehmen die kleinere. Zwei sortierte Stapel zusammenzufügen ist schnell: Jeder Vergleich bringt eine Rechnung an ihren Platz.

Und wie sortiert jede ihre Hälfte? Genauso: Sie teilt sie in zwei. Und so weiter, bis eine Rechnung übrig ist. Eine Rechnung ist schon sortiert.

Das ist Teile und herrsche (Divide and Conquer): Die Aufgabe wird in kleinere Aufgaben derselben Art zerlegt, sie werden mit derselben Methode gelöst, und ihre Antworten werden zusammengesetzt. Eine so gebaute Sortierung ist Mergesort.

Die Methode ruft sich selbst auf, also ist das Rekursion, wie in der Lektion „Rekursion“. Der Basisfall ist eine Liste mit einem Preis: Da gibt es nichts zu teilen.

Sieh es dir an

Bis auf einen Preis teilen und wieder zusammenfügen

mergeSort teilt und ruft sich für die zwei Hälften selbst auf. merge fügt zwei sortierte Teile zusammen. Sieh zu, wie die acht Preise bis auf einzelne hinuntergehen und die Merges sie auf dem Rückweg ordnen:

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

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

Schritt für Schritt, in Worten

mergeSort bekommt 8 Preise aus dem Katalog, ungeordnet.
mid = 4. slice legt zwei neue Arrays an: die linke Hälfte [45, 12, 80, 33] und die rechte Hälfte [7, 61, 25, 50].
Jede Hälfte ruft mergeSort für sich selbst auf und teilt wieder: 4 → 2 → 1.
Ein Teil mit einem Preis ist schon sortiert. Das ist der Basisfall: Ab hier beginnen die Aufrufe zurückzukehren.
merge fügt zwei sortierte Teile zusammen: Es vergleicht ihre ersten Preise und nimmt den kleineren. Für ein Paar ist das 1 Vergleich: 4 in der ganzen Reihe.
Aus den Paaren werden Vierergruppen. Jeder Vergleich schickt einen Preis nach unten, also braucht eine Reihe nie mehr Vergleiche, als sie Preise hat: hier 6.
Das letzte Zusammenfügen, [12, 33, 45, 80] mit [7, 25, 50, 61]. i und j zeigen auf den ersten noch nicht genommenen Preis jeder Seite: 7 Vergleiche, 7 Preise.
Eine Seite ist zu Ende. Was auf der anderen übrig ist (80), ist schon sortiert und geht ohne Vergleich ans Ende.
3 Ebenen des Teilens (8 → 4 → 2 → 1), und auf jeder Ebene geht das Zusammenfügen einmal durch jeden Preis: 4 + 6 + 7 = 17 Vergleiche. Bei n Preisen gibt es log₂ n Ebenen, also ist die Arbeit etwa n · log₂ n.

const prices = [45, 12, 80, 33, 7, 61, 25, 50];
console.log(`Vorher: [${prices.join(", ")}]`);
console.log(`Nachher: [${mergeSort(prices).join(", ")}]`);

Vorher: [45, 12, 80, 33, 7, 61, 25, 50]
Nachher: [7, 12, 25, 33, 45, 50, 61, 80]

slice(0, mid) legt ein neues Array mit den Elementen von 0 bis mid (ohne dieses) an. / in JavaScript liefert einen Bruch (9 / 2 ist 4.5), also rundet Math.floor ab.

Die Idee

Warum es n · log n ist

Sieh, was jeder Teil kostet:

Das Zusammenfügen ist O(n). Jeder Vergleich setzt einen Preis ins Ergebnis, und ist ein Teil leer, geht der Rest des anderen ohne Vergleich ans Ende. Zwei Teile mit zusammen n Preisen brauchen höchstens n − 1 Vergleiche.
Es gibt log₂ n Ebenen. Jede Ebene halbiert: 8 Preise ergeben 3 Ebenen (8 → 4 → 2 → 1), 100.000 Preise ergeben 17. log₂ n ist „wie oft sich n bis auf 1 halbiert“.
Auf jeder Ebene gehen die Merges einmal durch alle n Preise. Paare, Vierergruppen, Hälften: Die Gruppen unterscheiden sich von Ebene zu Ebene, aber zusammen sind es immer n.

Insgesamt: höchstens n · log₂ n Vergleiche. Bei 100.000 Preisen sind das unter 1.700.000. Bench zählt 1.536.292, etwa 1600-mal weniger als die 2,5 Milliarden von Insertionsort.

Probier es aus

Sage die Ausgabe voraus

Hier zählt merge seine Vergleiche. Die zwei Teile sind sortiert, und jeder Preis links ist kleiner als jeder Preis rechts:

let comparisons = 0;

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

console.log(`[${merge([10, 20, 30], [40, 50, 60]).join(", ")}]`);
console.log(`Vergleiche: ${comparisons}`);

Antwort

[10, 20, 30, 40, 50, 60]
Vergleiche: 3

[10, 20, 30, 40, 50, 60]
Vergleiche: 5

[10, 20, 30, 40, 50, 60]
Vergleiche: 6

Sieh es dir an

Miss es: Mergesort gegen Insertionsort

Lass beide Algorithmen auf demselben Preiskatalog laufen. Gezählt werden Vergleiche. Insertionsort läuft bei 100.000 nicht wirklich (die Seite würde einfrieren): Bench schätzt ihn aus der Kurve.

Insertion Sort O(n²)
Merge Sort O(n log n)

Algorithmus	n = 10	n = 1.000	n = 10.000	n = 100.000
Insertion Sort	32	256.555	24.738.716	≈ 2.473.871.600
Merge Sort	24	8.679	120.483	1.536.292

Der Code läuft in deinem Browser, in JavaScript. Die Zahl der Operationen ist in jeder Sprache gleich, weil der Algorithmus derselbe ist. Die Zeit hängt von der Maschine ab und dient nur zum Vergleich. „≈“ ist eine Schätzung anhand der Kurve: Ein so großes n führen wir nicht aus, damit die Seite nicht einfriert.

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

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

Bei 10 Preisen sind die zwei fast gleich. Bei 1000 macht Mergesort 8.679 Vergleiche gegen 256.555. Von da an wächst der Abstand mit jeder Null: Die O(n²)-Kurve ist doppelt so steil.

Genauer, für Neugierige

Dieselben Zahlen in deiner Sprache. Der Katalog kommt aus einem kleinen Generator mit Seed, ist also bei jedem Lauf, in jeder Sprache und in Bench derselbe. Der Zähler steigt bei jedem Vergleich zweier Preise:

let comparisons = 0;

function catalog(n) {
  const prices = [];
  let x = 2026;
  for (let k = 0; k < n; k++) {
    x = (x * 48271) % 2147483647;
    prices.push(1 + (x % 10000));
  }
  return prices;
}

function insertionSort(prices) {
  for (let i = 1; i < prices.length; i++) {
    const key = prices[i];
    let j = i;
    while (j > 0) {
      comparisons++;
      if (prices[j - 1] <= key) {
        break;
      }
      prices[j] = prices[j - 1];
      j--;
    }
    prices[j] = key;
  }
}

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

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

for (const n of [10, 1000]) {
  comparisons = 0;
  insertionSort(catalog(n));
  console.log(`insertion sort, n = ${n}: ${comparisons} Vergleiche`);
}
for (const n of [10, 1000, 100000]) {
  comparisons = 0;
  mergeSort(catalog(n));
  console.log(`merge sort, n = ${n}: ${comparisons} Vergleiche`);
}

insertion sort, n = 10: 32 Vergleiche
insertion sort, n = 1000: 256555 Vergleiche
merge sort, n = 10: 24 Vergleiche
merge sort, n = 1000: 8679 Vergleiche
merge sort, n = 100000: 1536292 Vergleiche

Die Idee

Der Preis: Speicher

Mergesort ist nicht umsonst. Insertionsort verschiebt die Preise in der Liste selbst und braucht keinen anderen Platz. Mergesort legt bei jeder Teilung neue Arrays an, und merge schreibt das Ergebnis in ein weiteres. Der zusätzliche Speicher ist O(n): bei 100.000 Preisen noch einmal so viel Platz.

Der Aufrufstapel ist flach: ein Frame pro Ebene, etwa log₂ n. Bei 100.000 Preisen sind das 18 Frames.

Gleiche Preise bleiben in der Reihenfolge, in der sie kamen: Bei Gleichstand nimmt merge den linken (<=). Das nennt man Stabilität, und sie hat eine eigene Lektion, „Stabiles Sortieren und die eingebaute Sortierung“.

In JavaScript legt slice immer ein neues Array an. Dieser Mergesort ist also kurz, kopiert aber viel. Das eingebaute sort in V8 ist TimSort, eine Variante des Mergesort, und viel schneller.

Probier es aus

Finde den Fehler

Ein Katalog mit acht Produkten geht hinein, und vier kommen heraus:

const prices = [45, 12, 80, 33, 7, 61, 25, 50];
console.log(`Vorher: [${prices.join(", ")}]`);
console.log(`Nachher: [${mergeSort(prices).join(", ")}]`);

Vorher: [45, 12, 80, 33, 7, 61, 25, 50]
Nachher: [33, 45, 50, 61]

In welcher Zeile steckt der Fehler?

Wähle die Zeile mit dem Fehler.

Probier es aus

Fülle die Lücke

Die Schleife in merge hört auf, sobald ein Teil leer ist. Was kommt in die Lücke, damit der Rest des rechten Teils ans Ende geht?

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

Übung

Zwei Lager, eine Preisliste

Löse die Aufgabe in deinem Editor.

Zwei Lager. Das Lager in Sofia und das Lager in Varna schicken ihre Preislisten, jede schon sortiert. Lies die zwei Zeilen und gib eine sortierte Preisliste für beide aus. Sortiere nicht noch einmal: Nutze merge aus der Lektion. Die Arbeit ist O(n), nicht O(n log n).

12 33 45 80
7 25 50 61 99

Gesamt: 7 12 25 33 45 50 61 80 99

Weitere Aufgaben

Zählen. Füge merge einen Zähler der Vergleiche hinzu und sortiere die acht Preise aus der Szene. Du solltest 17 bekommen.
Der teuerste zuerst. Ändere ein Zeichen, damit die Liste vom teuersten zum billigsten herauskommt.
Ohne Rekursion. Füge die benachbarten einzelnen Preise zu Paaren zusammen, dann die Paare zu Vierergruppen, dann die Vierer. Das ist Bottom-up-Mergesort: dieselben Vergleiche, ohne Aufrufstapel.

Genauer

Zusammenfügen außerhalb des Sortierens

Das Zusammenfügen sortierter Listen ist älter als Mergesort: Lochkartenmaschinen fügten schon in den 1930er Jahren sortierte Kartenstapel zusammen. Heute taucht es überall auf, wo die Daten schon sortiert sind: in git, in Datenbanken, in Dateien, die größer sind als der Speicher.

Genauer, für Neugierige

Git. Git hält den Inhalt jedes Ordners (einen Baum) nach Dateinamen sortiert. Wenn es zwei Versionen vergleicht oder Zweige zusammenführt, geht es die zwei sortierten Listen nebeneinander durch, wie merge: Ein Name, der nur auf einer Seite steht, ist eine hinzugefügte oder gelöschte Datei, und gleiche Namen sind eine Datei auf beiden Seiten, die verglichen wird. Einen Ordner zu prüfen ist also O(n), nicht eine Suche für jede Datei in der anderen Liste. Den Text in einer Datei zusammenzuführen ist ein anderer Algorithmus (diff), zu dem wir im Modul „Dynamische Programmierung“ kommen.

Externes Sortieren. Die Logs der Seite für ein Jahr sind 50 GB, und der Speicher hat 8 GB. Die Sortierung liest 1 GB auf einmal, sortiert es im Speicher und schreibt es als sortierten Block auf die Platte. Dann fügt sie die Blöcke zusammen: Von jedem liest sie nur die erste Zeile, nimmt die kleinste und macht weiter. Der Speicher reicht für eine Zeile aus jedem Block. So sortiert der Befehl sort unter Linux große Dateien, und PostgreSQL schreibt Sort Method: external merge in den Abfrageplan, wenn die Sortierung nicht in seinen Speicher passt.

Das Mastertheorem als Intuition. Die Zeit von Mergesort schreibt man T(n) = 2 · T(n/2) + n: zwei Aufgaben halber Größe plus n für das Zusammenfügen. Zeichne es als Baum: Oben gibt es n Arbeit, auf der nächsten Ebene zweimal n/2, das ist wieder n, und so weiter über log₂ n Ebenen. Insgesamt n · log₂ n. Das Mastertheorem verallgemeinert genau diesen Vergleich: Schrumpft die Arbeit pro Ebene nach unten, entscheidet die oberste Ebene; wächst sie, entscheiden die Blätter; ist sie auf jeder Ebene gleich, multiplizierst du mit der Zahl der Ebenen. Die binäre Suche ist T(n) = T(n/2) + 1: 1 pro Ebene, log₂ n Ebenen, O(log n).

Die eingebaute Sortierung. In JavaScript ist Array.prototype.sort in V8 (Chrome und Node) TimSort, eine Variante des Mergesort, die die schon sortierten Läufe in der Eingabe findet. Wie und warum, steht in der Lektion „Stabiles Sortieren und die eingebaute Sortierung“.

Test

Teste dich

1. Warum ist Mergesort O(n log n)?Er teilt in zwei, und das Teilen in zwei ist log nEr vergleicht jeden Preis mit jedem anderen, aber nur einmalDas Teilen ergibt log₂ n Ebenen, und das Zusammenfügen auf jeder Ebene geht einmal durch alle n Preise

2. merge fügt zwei sortierte Teile mit je 4 Preisen zusammen. Wie viele Vergleiche macht es höchstens?1687

3. Wofür zahlt Mergesort, was Insertionsort nicht kostet?Speicher: die Kopien der Hälften und das zusammengefügte Ergebnis, O(n) zusätzlichEr kann gleiche Preise nicht sortierenMehr Vergleiche bei großem n

4. Die acht Preise sind schon sortiert. Wie viele Vergleiche macht jeder?Insertionsort 28, Mergesort 17Je 7Insertionsort 7, Mergesort 12

5. Wie viele Ebenen des Teilens hat Mergesort bei 100.000 Preisen?17100.00050.000

Mergesort und „Teile und herrsche“

Cookies