Mergesort
Stabiles Sortieren
Mergesort ist eine kostenlose C Academy-Lektion auf CoddyKit. Dies ist Lektion 3 von 4. Du kannst die komplette Lektion unten kostenlos lesen – dann übst du sie direkt im Browser mit einem integrierten Code-Editor und einem KI-Tutor rund um die Uhr. Sie ist Teil des C Academy-Lernpfads, und dein Fortschritt wird über Web und CoddyKit-App synchronisiert. Der C Academy-Kurs umfasst insgesamt 4 Lektionen.
Stabiles Sortieren
Mergesort ist ein Divide-and-Conquer-Sortierverfahren, das das Array in zwei Hälften teilt, jede Hälfte sortiert und sie anschließend wieder zusammenführt. Es hat in jedem Fall die Laufzeit O(n log n) und ist stabil.
Der Teilungsschritt
Teilen Sie das Array rekursiv an der Mitte, bis jedes Teilstück ein Element enthält. Ein einzelnes Element ist trivialerweise sortiert und bildet den Basisfall.
Der Zusammenführungsschritt
Die Kernoperation führt zwei bereits sortierte Folgen zu einer einzigen zusammen. Durchlaufen Sie beide mit Indexzeigern und kopieren Sie jeweils als Nächstes das kleinere Element am Anfang.
#include <stdio.h>
void merge(int a[], int lo, int mid, int hi, int tmp[]) {
int i = lo, j = mid + 1, k = lo;
while (i <= mid && j <= hi)
tmp[k++] = (a[i] <= a[j]) ? a[i++] : a[j++];
while (i <= mid) tmp[k++] = a[i++];
while (j <= hi) tmp[k++] = a[j++];
for (int t = lo; t <= hi; t++) a[t] = tmp[t];
}
int main(void) {
int a[] = {1, 4, 6, 2, 3, 5}; /* two sorted runs */
int tmp[6];
merge(a, 0, 2, 5, tmp);
for (int i = 0; i < 6; i++) printf("%d ", a[i]);
printf("\n");
return 0;
}Warum das Verfahren stabil ist
Beim Zusammenführen wird a[i] <= a[j] verwendet. Sind zwei Elemente gleich, wird daher zuerst das Element aus der linken Folge übernommen. Da die linke Folge die früheren Elemente enthielt, bleibt die ursprüngliche Reihenfolge erhalten.
Der rekursive Aufruf
Mergesort ruft sich für jede Hälfte rekursiv auf und führt sie anschließend zusammen. Wir übergeben einen gemeinsamen temporären Puffer, um bei jedem Aufruf eine neue Speicherreservierung zu vermeiden.
#include <stdio.h>
void merge(int a[], int lo, int mid, int hi, int tmp[]) {
int i=lo, j=mid+1, k=lo;
while (i<=mid && j<=hi) tmp[k++] = (a[i]<=a[j]) ? a[i++] : a[j++];
while (i<=mid) tmp[k++]=a[i++];
while (j<=hi) tmp[k++]=a[j++];
for (int t=lo;t<=hi;t++) a[t]=tmp[t];
}
void msort(int a[], int lo, int hi, int tmp[]) {
if (lo >= hi) return;
int mid = lo + (hi - lo) / 2;
msort(a, lo, mid, tmp);
msort(a, mid + 1, hi, tmp);
merge(a, lo, mid, hi, tmp);
}
int main(void) {
int a[] = {5, 2, 9, 1, 3, 8, 4};
int tmp[7];
msort(a, 0, 6, tmp);
for (int i = 0; i < 7; i++) printf("%d ", a[i]);
printf("\n");
return 0;
}Speicherverbrauch
Im Gegensatz zu Quicksort benötigt Mergesort für den Puffer zum Zusammenführen zusätzlichen Speicher der Größe O(n). Das ist bei sehr großen Arrays und knappem Speicher der größte Nachteil.
Garantiertes O(n log n)
Die Rekursion teilt immer in zwei Hälften und erzeugt dadurch log n Ebenen. Auf jeder Ebene werden n Elemente zusammengeführt. Daher hat Mergesort im besten, durchschnittlichen und schlechtesten Fall die Laufzeit O(n log n) – im Gegensatz zu Quicksort.
Die Ebenen des Zusammenführens zählen
Die Anzahl der Rekursionsebenen beträgt ceil(log2 n). Berechnen wir sie für mehrere Größen.
#include <stdio.h>
int levels(int n) {
int L = 0;
while (n > 1) { n = (n + 1) / 2; L++; }
return L;
}
int main(void) {
int sizes[] = {1, 2, 8, 100, 1000};
for (int i = 0; i < 5; i++)
printf("n=%d levels=%d\n", sizes[i], levels(sizes[i]));
return 0;
}Bottom-Up-Mergesort
Eine iterative Variante führt Folgen der Größe 1, dann 2, dann 4 zusammen und verdoppelt die Größe bei jedem Durchlauf. Sie kommt vollständig ohne Rekursion aus und eignet sich gut für verkettete Listen.
#include <stdio.h>
void merge(int a[], int lo, int mid, int hi, int tmp[]) {
int i=lo,j=mid+1,k=lo;
while(i<=mid&&j<=hi) tmp[k++]=(a[i]<=a[j])?a[i++]:a[j++];
while(i<=mid) tmp[k++]=a[i++];
while(j<=hi) tmp[k++]=a[j++];
for(int t=lo;t<=hi;t++) a[t]=tmp[t];
}
int main(void) {
int a[] = {5, 2, 9, 1, 3, 8}, n = 6, tmp[6];
for (int width = 1; width < n; width *= 2)
for (int lo = 0; lo < n - width; lo += 2 * width) {
int mid = lo + width - 1;
int hi = (lo + 2*width - 1 < n-1) ? lo + 2*width - 1 : n-1;
merge(a, lo, mid, hi, tmp);
}
for (int i = 0; i < n; i++) printf("%d ", a[i]);
printf("\n");
return 0;
}Wann Sie Mergesort wählen sollten
Bevorzugen Sie Mergesort, wenn Sie Folgendes benötigen:
- Garantiertes O(n log n) ohne ungünstige Fälle
- Stabilität
- Das Sortieren verketteter Listen (kein wahlfreier Zugriff erforderlich)
- Externes Sortieren von Daten, die zu groß für den RAM sind
Mergesort im Vergleich zu Quicksort
Quicksort ist in der Praxis meist schneller und sortiert direkt im Array, ist aber bei einem ungünstigen Worst Case nicht stabil. Mergesort ist stabil und bietet eine garantierte Laufzeitgrenze, benötigt jedoch zusätzlichen Speicher. Entscheiden Sie anhand Ihrer Anforderungen.
Kurzer Test
Testen Sie Ihr Verständnis von Mergesort.
Zusammenfassung
Sie haben Mergesort kennengelernt.
- In zwei Hälften teilen, jede Hälfte sortieren und anschließend zusammenführen
- Beim Zusammenführen werden gleiche Schlüssel zuerst aus der linken Folge übernommen, wodurch Stabilität entsteht
- Garantiertes O(n log n) in allen Fällen
- Benötigt O(n) zusätzlichen Speicher und eignet sich besonders für verkettete Listen und externe Sortierung
Häufig gestellte Fragen
Ist die Lektion „Mergesort“ kostenlos?
Ja — der vollständige Text von „Mergesort“ ist hier im Web kostenlos zu lesen. Um sie interaktiv zu üben (integrierter Code-Editor und 24/7 KI-Tutor) und den Rest des C Academy-Kurses freizuschalten, upgrade auf CoddyKit PRO. Der C Academy-Kurs umfasst insgesamt 4 Lektionen.
Was lerne ich in „Mergesort“?
Stabiles Sortieren Du übst C Academy mit praktischem Code, den du direkt im Browser ausführst, und ein 24/7 KI-Tutor beantwortet deine Fragen während du die Lektion bearbeitest.
Brauche ich Erfahrung, um C Academy zu starten?
Keine Vorkenntnisse erforderlich. C Academy auf CoddyKit ist für Anfänger bis fortgeschrittene Lernende strukturiert, sodass du hier starten oder von Anfang an beginnen und in deinem eigenen Tempo voranschreiten kannst. Dies ist Lektion 3 von 4.
Wie lange dauert die Lektion „Mergesort“?
Die meisten CoddyKit-Lektionen dauern etwa 5–10 Minuten. Jede ist kompakt und interaktiv, sodass du stetig Fortschritte machst und genau dort weitermachst, wo du aufgehört hast – im Web und in der App.
Kann ich in dieser C Academy-Lektion Code schreiben und ausführen?
Ja. Jede C Academy-Lektion enthält einen integrierten Code-Editor, sodass du echten Code direkt in deinem Browser schreibst und ausführst und sofort KI-Feedback erhältst — ohne lokale Einrichtung erforderlich.