Was wir schon wissen

Lernziele

Warum reicht O(n²) nicht?

Konkrete Laufzeit bei 1 Milliarde Operationen pro Sekunde (eine moderne CPU):

Die Idee: Teile und herrsche

Ein uralter Trick — schon die Römer haben so regiert: divide et impera. In der Informatik heißt das:

Warum log n? — der Halbierungs-Baum

Wenn wir n=16 immer wieder halbieren, sind wir in 4 Schritten bei 1. Das ist log₂(16) = 4.

Teile & herrsche kennt ihr schon

Kurzer Einschub: Rekursion

Bevor wir Merge Sort und Quicksort schreiben — ein Konzept, das wir brauchen.

Rekursion-Beispiel: Fakultät

Mathematisch: 5! = 5 · 4 · 3 · 2 · 1 = 120. Aber auch: 5! = 5 · 4! — und dasselbe Muster wiederholt sich nach innen.

int fakt(int n) {
    if (n <= 1) {
        return 1;         // Basis
    }
    return n * fakt(n - 1);  // ruft sich selbst
}

Call-Stack — Phase 1: Stack wächst (Push)

Jeder Aufruf von fakt bekommt ein eigenes Stockwerk (Stack-Frame). Solange ein Aufruf noch wartet, bleibt sein Frame liegen — gestapelt wie Teller, der neueste oben drauf (push).

Call-Stack — Phase 2: Stack schrumpft (Pop)

Sobald die Basis erreicht ist, „klappen" die Frames von oben nach unten wieder zu. Jeder Frame nutzt seine gepufferten Werte und das Ergebnis von oben, um seine eigene Rechnung fertigzustellen.

Merge Sort — die Grundidee

Drei Schritte — Schritt 2 ist rekursiv (genau das Konzept von eben):

Merge Sort — Phase 1: Aufteilen

Beispiel mit 8 Karten: [ 5, 2, 8, 1, 9, 3, 7, 4 ]

Bei 8 Karten: 3 Halbierungen (log₂ 8 = 3).

Das Werkzeug: der Verschmelz-Trick

Merge Sort — Phase 2: den Trick auf allen Ebenen anwenden

Jetzt wenden wir das Werkzeug von Slide 9 nicht nur einmal an, sondern immer wieder — Ebene für Ebene, bis das ganze Array eine sortierte Liste ist. Aufteilen + Trick allein reichen nicht; erst die Wiederholung des Tricks macht das Sortieren komplett.

✓ 3 Stufen · jede Stufe verschmilzt alle 8 Karten · zusammen ca. n × log n Vergleiche

Merge Sort — Stufen-Übersicht

Schauen wir das Aufteilen einmal von oben: aus einer großen Liste werden in jeder Stufe doppelt so viele, halb so große Häufchen.

Merge Sort — Pseudocode (rekursiv)

Drei Zeilen sind das Herz: halbieren · sich selbst auf jede Hälfte aufrufen · verschmelzen.

// Sortiert den Abschnitt a[links..rechts]
function mergeSort(a, links, rechts):
    if links >= rechts:
        return                            // Basis-Fall: 0 oder 1 Element ist sortiert

    mitte = (links + rechts) / 2
    mergeSort(a, links, mitte)             // linke Hälfte weiter teilen (sich selbst rufen)
    mergeSort(a, mitte + 1, rechts)        // rechte Hälfte weiter teilen
    merge(a, links, mitte, rechts)         // HIER wird sortiert: vergleichen + verschmelzen

// Hilfs-Funktion: verschmilzt a[links..mitte] und a[mitte+1..rechts]
// (genau der Trick aus Slide 9 — vorderste Karten vergleichen)
function merge(a, links, mitte, rechts):
    // → siehe nächste Slide (C-Code)

Merge Sort in C — die merge-Funktion

Erst die Hilfs-Funktion: verschmilzt a[l..m] und a[m+1..r] — beide sind bereits sortiert.

void merge(int a[], int l, int m, int r) {
    int hilfs[1024];          // Hilfs-Array für das Ergebnis
    int i = l;                  // Zeiger auf vorderstes Element links
    int j = m + 1;              // Zeiger auf vorderstes Element rechts
    int k = 0;                  // Schreib-Position in hilfs[]

    // Solange beide Hälften noch Elemente haben: nimm das kleinere
    while (i <= m && j <= r) {
        if (a[i] <= a[j]) {
            hilfs[k] = a[i];
            i = i + 1;
        } else {
            hilfs[k] = a[j];
            j = j + 1;
        }
        k = k + 1;
    }
    // Rest übernehmen (immer nur eine der beiden Schleifen läuft)
    while (i <= m) { hilfs[k] = a[i]; i = i + 1; k = k + 1; }
    while (j <= r) { hilfs[k] = a[j]; j = j + 1; k = k + 1; }

    // Hilfs-Array zurück in a[l..r] kopieren
    for (int x = 0; x < k; x = x + 1) {
        a[l + x] = hilfs[x];
    }
}

Merge Sort in C — die rekursive Hauptfunktion

Drei Zeilen Logik — exakt das Pseudocode-Muster von Slide 11. Die Funktion ruft sich für jede Hälfte selbst auf.

// Sortiert a[l..r] rekursiv
void merge_sort(int a[], int l, int r) {
    if (l >= r) {
        return;                       // Basis-Fall
    }
    int m = (l + r) / 2;            // Mitte

    merge_sort(a, l, m);              // links weiter teilen
    merge_sort(a, m + 1, r);          // rechts weiter teilen
    merge(a, l, m, r);                // HIER wird sortiert!
}

// Aufruf für ein Array a der Länge n:
//   merge_sort(a, 0, n - 1);

merge_sort(a, 0, 7);    // ✓ richtig
merge_sort(a[], 0, 7);  // ✗ Fehler
merge_sort(a[0], 0, 7); // ✗ a[0] ist 5!

„Aber wo wird denn jetzt sortiert?"

Beim Lesen der drei Zeilen merge_sort(...) · merge_sort(...) · merge(...) denkt jeder: „die ersten zwei machen doch nichts — die rufen sich nur selbst auf!" Genau richtig:

Merge Sort in C — das komplette Programm

Alles zusammen in einer Datei merge_sort.c — kopier-und-kompilier-fertig. Erinnerung: merge_sort teilt auf · merge sortiert beim Zusammenfügen.

#include <stdio.h>

// WERKZEUG: nimmt 2 sortierte Teile, macht daraus 1 sortierten Teil
void merge(int a[], int l, int m, int r) {
    int hilfs[1024];
    int i = l, j = m + 1, k = 0;       // Zeiger links/rechts/hilfs
    while (i <= m && j <= r) {           // kleinere von beiden nehmen
        if (a[i] <= a[j]) { hilfs[k] = a[i]; i++; }
        else              { hilfs[k] = a[j]; j++; }
        k++;
    }
    while (i <= m) { hilfs[k] = a[i]; i++; k++; }   // Rest links
    while (j <= r) { hilfs[k] = a[j]; j++; k++; }   // Rest rechts
    for (int x = 0; x < k; x++) a[l + x] = hilfs[x];
}

// SORTIERER: ruft sich rekursiv für jede Hälfte auf, dann merge
void merge_sort(int a[], int l, int r) {
    if (l >= r) return;                // Basis: 0/1 Element ist sortiert
    int m = (l + r) / 2;
    merge_sort(a, l, m);                // linke Hälfte weiter teilen
    merge_sort(a, m + 1, r);            // rechte Hälfte weiter teilen
    merge(a, l, m, r);                  // HIER wird sortiert!
}

int main(void) {
    int a[] = {5, 2, 8, 1, 9, 3, 7, 4};
    int n = 8;
    merge_sort(a, 0, n - 1);            // ganzes Array sortieren
    for (int i = 0; i < n; i++) printf("%d ", a[i]);
    printf("\n");                          // → 1 2 3 4 5 7 8 9
    return 0;
}

$ gcc merge_sort.c -o ms
$ ./ms
1 2 3 4 5 7 8 9

Warum braucht Merge Sort O(n log n)?

O(n²) vs. O(n log n) — visuell

Operationen für verschiedene Eingabegrößen (Balkenlänge proportional zur Operations-Anzahl, log-skaliert):

Die vier Sortier-Algorithmen im Vergleich

Was nutzen echte Sprachen intern?

🤔 Quiz

Zusammenfassung

📚 Vertiefung bis nächste Woche