Der Merge-Sort-Algorithmus

Quicksort erreicht O(n log n), indem es um ein aus den Daten selbst gewähltes Pivot herum partitioniert — genau das lässt seinen Worst Case von der Eingabereihenfolge abhängen. Merge Sort erreicht dieselbe Komplexität auf anderem Weg, mit einer Garantie, die Quicksort nicht geben kann: Es ist jedes Mal O(n log n), egal wie die Eingabe angeordnet ist — auf Kosten eines zweiten Arrays, in dem gearbeitet wird.

Die Idee

Eine Liste mit einem Element ist bereits sortiert. Zwei sortierte Listen lassen sich zu einer größeren sortierten Liste verschmelzen, indem man wiederholt das jeweils kleinere der beiden vorderen Elemente nimmt — dieser Kombinationsschritt heißt Merge und braucht nur einen Durchlauf durch beide Listen, sodass das Verschmelzen zweier Läufe der Länge m insgesamt O(m) Arbeit kostet, nicht O(m log m).

Top-down-Merge-Sort wendet das rekursiv an: die Liste halbieren, jede Hälfte (rekursiv) sortieren, dann die beiden sortierten Hälften verschmelzen. Das Sample unten baut dasselbe Ergebnis stattdessen bottom-up auf, was die Rekursion komplett überflüssig macht: Zunächst wird jedes einzelne Element als bereits "sortiert" behandelt (ein Lauf der Länge 1), dann werden wiederholt benachbarte Läufe zu doppelt so großen Läufen verschmolzen — Länge 1 zu Länge 2, Länge 2 zu Länge 4 und so weiter — bis ein Lauf das gesamte Array abdeckt. Dass sich die Lauflänge bei jedem Durchgang verdoppelt, ist genau der Grund, warum es nur log₂ n Durchgänge gibt.

Implementierung

#include "plot.hpp"
#include <stdlib.h>

const int N = 20;
int values[N];
int temp[N];

int width = 1; // size of each run being merged this pass
int lo, mid, hi;
int p, q, k;    // left run pointer, right run pointer, write pointer
bool merging = false;
bool done = false;
int tick = 0;

void setup() {
    PlotCanvas(640, 480);

    for (int n = 0; n < N; n++) {
        values[n] = n + 1;
    }

    srand(1);
    for (int n = N - 1; n > 0; n--) {
        int r = rand() % (n + 1);
        int tmp = values[n];
        values[n] = values[r];
        values[r] = tmp;
    }

    lo = 0;
}

void frame() {
    // Slow the animation down: one step every few calls to frame() instead
    // of one per call, so individual comparisons stay visible.
    if (!done && ++tick >= 4) {
        tick = 0;

        if (!merging) {
            if (width >= N) {
                done = true;
            } else if (lo >= N) {
                width *= 2;
                lo = 0;
                if (width >= N) done = true;
            } else {
                mid = lo + width;
                if (mid > N) mid = N;
                hi = lo + 2 * width;
                if (hi > N) hi = N;

                if (mid >= hi) {
                    lo += 2 * width; // right run empty, nothing to merge here
                } else {
                    p = lo;
                    q = mid;
                    k = lo;
                    merging = true;
                }
            }
        } else {
            if (p < mid && (q >= hi || values[p] <= values[q])) {
                temp[k] = values[p];
                p++;
            } else {
                temp[k] = values[q];
                q++;
            }
            k++;

            if (k >= hi) {
                for (int n = lo; n < hi; n++) {
                    values[n] = temp[n];
                }
                lo += 2 * width;
                merging = false;
            }
        }
    }

    PlotBackground(250, 250, 250);

    int barWidth = plot_width / N;
    for (int idx = 0; idx < N; idx++) {
        int v;
        if (done) {
            PlotColor(70, 170, 90);   // fully sorted
            v = values[idx];
        } else if (merging && idx >= lo && idx < hi) {
            if (idx < k) {
                PlotColor(70, 170, 90);   // already merged this pass
                v = temp[idx];
            } else if (idx == p || idx == q) {
                PlotColor(220, 60, 60);   // heads currently being compared
                v = values[idx];
            } else {
                PlotColor(30, 100, 200);  // waiting in its run
                v = values[idx];
            }
        } else {
            PlotColor(30, 100, 200);      // not part of the active merge
            v = values[idx];
        }

        int height = v * (plot_height - 20) / N;
        int x0 = idx * barWidth + 1;
        int x1 = x0 + barWidth - 2;
        int y0 = plot_height - height;
        int y1 = plot_height;
        PlotFilledRectangle(x0, y0, x1, y1);
    }
}

width ist die aktuelle Lauflänge; ein vollständiger Durchgang verschmilzt jedes benachbarte Paar von width-großen Läufen, danach verdoppelt sich width für den nächsten Durchgang. Innerhalb eines Merges sind p und q das nächste noch nicht verschmolzene Element des linken bzw. rechten Laufs, k ist die Schreibposition im Hilfsarray temp, und jeder Schritt vergleicht einfach values[p] mit values[q] und hängt den kleineren Wert an. Ist ein Laufpaar vollständig verschmolzen, wird es blockweise aus temp zurück in values kopiert, und lo rückt zum nächsten Paar vor.

Da ein Merge immer nur aus dem Originalarray liest und in temp schreibt, kann die Visualisierung zeigen, wie ein Lauf schon vor dem Zurückkopieren korrekt verschmolzen an Ort und Stelle wächst — das ist das wachsende grüne Segment innerhalb des aktiven Fensters:

• blau — nicht Teil des gerade laufenden Merges
• rot — die beiden Laufköpfe, die gerade verglichen werden
• grün — in diesem Durchgang bereits in temp verschmolzen (alle Balken werden kurz auf einmal grün, sobald das gesamte Array ein sortierter Lauf ist)

Schritt für Schritt durchgerechnet

Das Verschmelzen der beiden bereits sortierten Läufe [1, 4] und [2, 8]:

Ergebnis: [1, 2, 4, 8]. Jedes der vier Elemente wird genau einmal betrachtet — kein erneutes Durchsuchen — was einen Merge bei O(m) für zwei Läufe der Gesamtlänge m hält, und den gesamten Durchgang bei O(n) für alle Läufe einer gegebenen Breite zusammen.

Warum sich das zusätzliche Array lohnt

Merge Sorts O(n log n)-Grenze gilt bedingungslos, anders als bei Quicksort, weil das Verschmelzen nie davon abhängt, wie die Daten zufällig angeordnet sind — nur davon, wie viele Elemente es sind. Diese Vorhersagbarkeit ist wertvoll genug, dass Merge Sort (oder eine Hybridform davon) der Standard-Sort für Daten ist, bei denen der Worst Case wichtig ist, oder bei denen Stabilität gefordert ist — gleiche Elemente behalten ihre relative Reihenfolge, da der Merge-Schritt bei Gleichstand immer den linken Lauf bevorzugt.

Der Preis ist das temp-Array: Merge Sort braucht O(n) zusätzlichen Speicher, wo Quicksort und die einfachen Sortierverfahren keinen brauchen. Es bewegt in der Praxis auch tendenziell mehr Daten als Quicksorts In-place-Partitionierung, was der Hauptgrund ist, warum Quicksort bei typischen Eingaben meist schneller ist, obwohl beide im Schnitt O(n log n) sind. Wo Merge Sort klar gewinnt, ist das externe Sortieren — das Sortieren von Daten, die nicht in den Speicher passen — da das Verschmelzen sequenziell von der Festplatte gelesener sortierter Blöcke seinen Stärken weit besser entgegenkommt als Quicksorts Zugriffsmuster mit wahlfreiem Zugriff.

Fazit

Über diese Serie hinweg erzeugt dieselbe zugrunde liegende Idee — Sortieren auf Vergleiche und Umordnungen zurückführen — sehr unterschiedliche Algorithmen, je danach, wie die Arbeit strukturiert ist: Nachbarn wiederholt durchsuchen, einen sortierten Präfix wachsen lassen, oder das Problem teilen und die Ergebnisse kombinieren. Merge Sorts Beitrag ist eine Garantie: Egal wie die Eingabe aussieht, das Verschmelzen sortierter Läufe kostet genau das, was es kostet, und nicht mehr.