Merge-Sort-Vergleiche: Worst Case und Durchschnitt

Er liefert den exakten Worst Case, den Erwartungswert bei gleichverteilter zufälliger Reihenfolge, die Anzahl rekursiver Ebenen und n mal den Logarithmus von n zur Basis 2 als Referenz. So können Sie das linearithmische Wachstum konkret erkennen und von quadratischem Sortierverhalten unterscheiden.

Was der Rechner zählt

Berücksichtigt werden Ordnungsvergleiche zwischen Elementen während des Zusammenführens, also die zentrale Operation der üblichen Merge-Sort-Analyse. Indexprüfungen, Zuweisungen, Schreibvorgänge in temporäre Arrays, rekursive Aufrufe, Speicherbelegungen und interne Arbeit eines anwendungsspezifischen Vergleichers zählen nicht dazu. Ein einzelnes Element benötigt keinen Vergleich. Bei größeren Eingaben teilt der Algorithmus den Bereich, sortiert beide Teile und vergleicht wiederholt deren erste noch nicht verbrauchte Elemente. Das Zusammenführen von Gruppen mit a und b Elementen erfordert höchstens a plus b minus einen Vergleich, weil das letzte verbleibende Element ohne weiteren Vergleich kopiert werden kann. Der Worst Case wendet diese Regel auf den tatsächlichen Teilungsbaum an, auch wenn n keine Zweierpotenz ist. Verwenden Sie n_log2_n daher als Größenreferenz und die Vergleichsfelder als operative Schätzwerte.

Herleitung von Worst Case und Durchschnitt

Die exakte Worst-Case-Formel lautet: n mal die aufgerundete Zahl des Logarithmus von n zur Basis 2, minus zwei hoch dieser Zahl, plus eins. Sie beschreibt einen üblichen binären Merge Sort mit möglichst gleichmäßig geteilten Teilarrays. Der Durchschnitt ist ein Erwartungswert über gleichverteilt zufällige Permutationen verschiedener Schlüssel. Beim Zusammenführen von Folgen mit a und b Elementen beträgt er a plus b, minus a geteilt durch b plus eins, minus b geteilt durch a plus eins. Der Rechner summiert diese Kosten rekursiv über denselben ausgeglichenen Baum und rundet nur die angezeigte Endzahl auf sechs Dezimalstellen. Ein Erwartungswert darf gebrochen sein, obwohl jeder konkrete Lauf ganzzahlig viele Vergleiche ausführt. Doppelte Schlüssel, andere Gleichstandsregeln, natürliche Läufe oder Schwellen für Insertion Sort können den beobachteten Wert verändern.

Das linearithmische Ergebnis einordnen

n_log2_n zeigt die typische linearithmische Skala. Jede weitere Zusammenführungsebene verarbeitet alle n Elemente, während die Zahl der Ebenen nur logarithmisch wächst. Die beiden Verhältnisfelder teilen die Schätzwerte durch n mal den Logarithmus von n zur Basis 2. Damit sehen Sie für n größer als eins, wie nah die konkreten Werte an dieser Referenz liegen. Diese Angaben sind beschreibend, weder Komplexitätsbeweis noch Hardware-Benchmark. Speicherverkehr, Allokationen, Vergleicherkosten, Cache und Laufzeitumgebung können die reale Dauer bestimmen. Testen Sie Werte unmittelbar unter und über Zweierpotenzen. An diesen Grenzen ändert sich die Rekursionstiefe; zugleich wird sichtbar, warum die O-Notation Konstanten und Terme niedrigerer Ordnung ausblendet, obwohl diese für eine konkrete Eingabe weiterhin relevant sind.