Vergleiche
Schreibvorgänge
Verschmelzungen

  • Wird verschmolzen
  • Verglichen
  • Zurückgeschrieben
  • Bisher verschmolzen

Mehr über Mergesort

Mergesort

Mergesort ist ein Teile-und-herrsche-Algorithmus. Er halbiert die Liste, sortiert jede Hälfte auf dieselbe Weise und verschmilzt die beiden sortierten Hälften, indem er immer wieder den kleineren vorderen Wert nimmt. Sehen Sie, wie die Hälften in eine Pufferzeile kommen und geordnet zurückgeschrieben werden, in beliebigem Tempo oder Schritt für Schritt, und zählen Sie Vergleiche, Schreibvorgänge und Verschmelzungen. Drücken Sie „Abspielen“, um die Sortierung anzusehen, oder gehen Sie mit „Schritt“ und „Zurück“ einen Schritt nach dem anderen durch. Ziehen Sie den Schrittregler, um an eine beliebige Stelle zu springen. Die Kacheln zählen Vergleiche, Schreibvorgänge in die Liste und Verschmelzungen. Wählen Sie die Anzahl der Balken und ihre Startreihenfolge, oder geben Sie eigene Zahlen ein. Ist das Feld ausgewählt, gehen die Pfeiltasten schrittweise vor, die Leertaste startet und pausiert, und Pos1 und Ende springen zum Anfang und zum Ende.

Wie es funktioniert

  1. Wählen Sie die Anzahl der Balken und ihre Startreihenfolge: zufällig, fast sortiert, umgekehrt oder mit wenigen verschiedenen Werten. Oder geben Sie eigene Zahlen ein.
  2. Drücken Sie „Abspielen“ oder gehen Sie mit „Schritt“ und „Zurück“ einen Schritt nach dem anderen durch. Ziehen Sie den Schrittregler, um an eine beliebige Stelle der Sortierung zu springen.
  3. Verfolgen Sie jede Verschmelzung: Die beiden sortierten Hälften gehen hinunter in den Puffer, und der kleinere vordere Wert geht wieder hinauf, einer nach dem anderen.

So funktioniert Mergesort

Ein einzelner Wert ist schon sortiert. Bei allem Längeren wird die Liste in zwei Hälften geteilt und jede Hälfte mit Mergesort sortiert. Dann werden sie verschmolzen: Man schaut auf den vorderen Wert jeder Hälfte, übernimmt den kleineren ins Ergebnis und wiederholt das, bis beide Hälften leer sind. Weil beide Hälften sortiert sind, ist auch das Ergebnis sortiert.

Immer n log n

Durch wiederholtes Halbieren entstehen etwa log₂ n Ebenen, und jede Ebene von Verschmelzungen schreibt jeden Wert einmal. So macht die Sortierung etwa n log₂ n Schreibvorgänge und höchstens ebenso viele Vergleiche. Anders als bei Bubblesort, Selectionsort und Insertionsort wächst das nicht mit n², und die Reihenfolge der Liste spielt eine viel kleinere Rolle. Der Preis ist ein Puffer so lang wie die Liste. Mergesort ist außerdem stabil und deshalb die Grundlage der Sortierverfahren in Python und Java.

Häufig gestellte Fragen

Wie funktioniert Mergesort?

Mergesort halbiert die Liste, sortiert jede Hälfte mit Mergesort und verschmilzt die beiden sortierten Hälften, indem es immer wieder den kleineren ihrer vorderen Werte nimmt. Eine Liste mit einem Wert ist schon sortiert, dort endet das Teilen.

Wie viele Vergleiche macht Mergesort?

Bei n Werten höchstens etwa n log₂ n − n + 1 und mindestens etwa die Hälfte von n log₂ n. Bei 40 Werten sind es höchstens 177. Die Schreibvorgänge in die Liste sind für ein gegebenes n immer gleich: einer pro Wert auf jeder Verschmelzungsebene.

Warum braucht Mergesort zusätzlichen Speicher?

Zwei Hälften direkt in der Liste zu verschmelzen, ist schwer schnell zu machen. Daher kopiert die übliche Variante von Mergesort die Hälften in einen Puffer und schreibt sie geordnet zurück. Der Puffer ist so lang wie die Liste, das ist der größte Nachteil gegenüber Quicksort und Heapsort.

Ist Mergesort stabil?

Ja. Sind die beiden vorderen Werte gleich, kommt der aus der linken Hälfte zuerst, so behalten gleiche Werte ihre ursprüngliche Reihenfolge.

Werden meine Zahlen irgendwohin gesendet?

Nein. Die Sortierung läuft in Ihrem Browser, und Ihre letzten Einstellungen bleiben im lokalen Speicher dieses Browsers.

Bereit, es auszuprobieren?

Öffnen Sie PictorX in Ihrem Browser – keine Installation, zum Starten ist keine Kreditkarte erforderlich.

Zum Editor