# 3.6 Merge Sort

Quelle: https://inf.zone/lectures/3-algorithmen/short-3-6-merge-sort/

## Video

[Video ansehen (1080p)](https://videos.inf.zone/58ff9c98eb7cd981/short-3-6-merge-sort-1080p.mp4) · [Video (720p)](https://videos.inf.zone/58ff9c98eb7cd981/short-3-6-merge-sort-720p.mp4) · [Video (480p)](https://videos.inf.zone/58ff9c98eb7cd981/short-3-6-merge-sort-480p.mp4) · [Video auf YouTube](https://youtu.be/ByXjH23FSdw)

## Hinweise zu diesem Video

**Korrekturen**

Die Korrekturen betreffen das Video. In den Folien zum Herunterladen sind sie eingearbeitet, soweit sie die Folien betreffen.

- Folie 17: Der Code teilt ein Array ungerader Länge so, dass die linke Hälfte die längere ist ([5, 2] und [1]). Das Beispiel der Folien 4 bis 14 teilt umgekehrt ([5] und [2, 1]). Beide Regeln sind richtig, der Ablauf unterscheidet sich.

## Material

- [Folien](https://inf.zone/download/lectures/3-algorithmen/3.6-merge-sort.pdf)
- Folien und Transkript: unten auf dieser Seite
- [Schrittliste](https://inf.zone/download/lectures/3-algorithmen/3.6-schrittliste.txt)

## Folien und Transkript

*Folientext aus den PDF-Folien, darunter jeweils der gesprochene Text des Videos. Der gesprochene Text ist maschinell transkribiert und nachkorrigiert, kann aber noch Fehler enthalten; im Video sprechen abwechselnd Prof und eine AI-Figur, die Sprecherwechsel sind nicht markiert. Die Zuordnung zu den Folien ist ungefähr. Die Zeitangaben verlinken auf die Stelle im Video (YouTube). Maßgeblich sind Video und Folien.*

### Folie 1 — Merge Sort

[Folie 1 als PDF](https://inf.zone/download/lectures/3-algorithmen/3.6-merge-sort.pdf#page=1)

#### Transkript

**[Video 00:00–00:35](https://www.youtube.com/watch?v=ByXjH23FSdw&t=0)**

Dies ist Inf-Einf-B. Heute Merge Sort. Heute sprechen wir über einen sehr eleganten Sortieralgorithmus, der zusätzlichen Platz braucht, um Ordnung zu schaffen. Na, wie bei meinem Büro. Ich bräuchte eigentlich auch ein zweites, um alles temporär zwischenzulagern und dann ordentlich zurückzuräumen. Genau. Nur dass Merge Sort im Gegensatz zu gewissen Büros den Sortiervorgang auch tatsächlich abschließt. Ja, ist gut jetzt. Na gut.

### Folie 2

[Folie 2 als PDF](https://inf.zone/download/lectures/3-algorithmen/3.6-merge-sort.pdf#page=2)

Bei Merge Sort ist die Grundidee, kleinere Arrays zu sortieren und diese Arrays dann sortiert zusammenzuführen (zu mergen). Merge Sort nutzt dabei Rekursion.

Wie sortiert man ein Array mit Merge Sort? →Durch Aufruf von Merge Sort auf beiden Hälften!

```text
MergeSort(Array)
├── MergeSort(linke Hälfte)
└── MergeSort(rechte Hälfte)
```

#### Transkript

*Kein Transkriptabschnitt eindeutig dieser Folie zugeordnet. Möglicherweise eine Aufbau-/Grafikfolie oder eine Abweichung zwischen PDF und Video.*

### Folie 3 — Pseudocode

[Folie 3 als PDF](https://inf.zone/download/lectures/3-algorithmen/3.6-merge-sort.pdf#page=3)

A. Prüfe Basisfall

Ist das Array einelementig? Dann ist es bereits sortiert!

B. Teile (Divide)

Teile Array in zwei Hälften.

C. Sortiere rekursiv (Conquer)

Rufe MergeSort auf beiden Hälften auf.

D. Führe zusammen (Combine)

Merge die sortierten Hälften.

#### Transkript

> Zuordnung unsicher: wenige gemeinsame Textmerkmale; anhand der benachbarten Folien eingeordnet.

**[Video 00:00–00:35](https://www.youtube.com/watch?v=ByXjH23FSdw&t=0)**

Also fangen wir an.

### Folie 4 — Beispiel

[Folie 4 als PDF](https://inf.zone/download/lectures/3-algorithmen/3.6-merge-sort.pdf#page=4)

```text
MergeSort([5, 2, 1, 3, 6, 4])
|
├── MergeSort([5, 2, 1])      ←
|   ├── MergeSort([5])
|   └── MergeSort([2, 1])
|
└── MergeSort([3, 6, 4])
    ├── MergeSort([3])
    └── MergeSort([6, 4])

Erste Teilung
```

A. Array einelementig? Dann ist es sortiert!

B. Teile Array in zwei Hälften.

C. Rufe Merge Sort auf beiden Hälften auf.

D. Merge die sortierten Hälften.

#### Transkript

**[Video 00:00–00:35](https://www.youtube.com/watch?v=ByXjH23FSdw&t=0)**

Nachdem wir jetzt bereits zwei einfache Sortieralgorithmen kennengelernt haben, wenden wir uns heute einem eleganten Verfahren zu.

**[Video 00:35–01:06](https://www.youtube.com/watch?v=ByXjH23FSdw&t=35)**

Merge Sort, elegant, erinnern Sie sich? Das Wort haben wir im Video zur Rekursion eingeführt. Und ja, Merge Sort ist so ein elegantes Verfahren. Die Grundidee ist bestechend einfach. Wir teilen ein großes Problem in kleinere Teilprobleme auf, bis wir bei trivialen Problemen ankommen. Konkret bedeutet das: Statt ein großes Array auf einmal zu sortieren, teilen wir es in kleinere Arrays auf. Und zwar so lange, bis wir bei Arrays der Größe eins ankommen. Die zu sortieren ist ja nicht besonders schwer. Und dann führen wir die kleinen sortierten Arrays nach und nach

**[Video 01:06–01:33](https://www.youtube.com/watch?v=ByXjH23FSdw&t=66)**

zum Gesamtarray zusammen. Auf Englisch sagt man dann, wir mergeen die Arrays. Genau. Merge Sort ist ein Verfahren, das auf dem Teile-und-herrsche-Prinzip basiert. Dieses Konzept taucht in vielen Algorithmen auf. Wir haben es zum Beispiel auch bei der binären Suche gesehen. In der Tat. Also. Im Pseudocode sieht das Ganze sehr übersichtlich aus. Nur drei Schritte, die wir gleich im Detail betrachten werden. Bevor wir in die Details von Merge Sort einsteigen, lassen Sie uns kurz das praktische Problem betrachten, das wir lösen wollen. Stellen Sie sich vor,

**[Video 01:33–02:04](https://www.youtube.com/watch?v=ByXjH23FSdw&t=93)**

Sie entwickeln ein Lagerverwaltungssystem für einen Online-Händler. Tausende von Artikeln, jeder mit einer eindeutigen Nummer, müssen schnell gefunden werden können. Neue Artikel kommen ständig hinzu. Um effizient suchen zu können, zum Beispiel mit binärer Suche, brauchen wir ein sortiertes Array. Und genau hier kommt Merge Sort ins Spiel. Genau, ein sehr anschauliches Beispiel. In der Praxis würde man natürlich fortgeschrittenere Datenstrukturen verwenden, aber für das Verständnis der Grundprinzipien arbeiten wir hier nur mit einem einfachen Array. Fünf, zwei, eins, drei, sechs und vier.

**[Video 02:04–02:42](https://www.youtube.com/watch?v=ByXjH23FSdw&t=124)**

Exakt. Und wie wir sehen werden, ist Merge Sort für dieses Problem besonders gut geeignet. Also nicht nur theoretisch elegant, sondern auch praktisch effizient. Beginnen wir also mit unserem Array 5 2 1 3 6 4. Merge Sort folgt einem einfachen, aber genialen Prinzip. Um ein Array zu sortieren, teilen wir es in zwei Hälften und sortieren jede Hälfte durch einen erneuten Aufruf von Merge Sort. Das klingt zunächst zirkulär, aber Sie werden gleich sehen, wie elegant das funktioniert.

### Folie 5 — Beispiel

[Folie 5 als PDF](https://inf.zone/download/lectures/3-algorithmen/3.6-merge-sort.pdf#page=5)

```text
MergeSort([5, 2, 1])
├── MergeSort([5]) ✓
└── MergeSort([2, 1])      ←
    ├── MergeSort([2])
    └── MergeSort([1])

A: Basisfall? Nein, 2 Elemente
B: Teile in [2] und [1]
C: Rekursive Aufrufe
```

A. Array einelementig? Dann ist es sortiert!

B. Teile Array in zwei Hälften.

C. Rufe Merge Sort auf beiden Hälften auf.

D. Merge die sortierten Hälften.

#### Transkript

**[Video 02:04–02:42](https://www.youtube.com/watch?v=ByXjH23FSdw&t=124)**

Jeder Aufruf von Merge Sort durchläuft genau diese vier Schritte. Erst prüfen wir, ob der Basisfall vorliegt. Ist das Array einelementig, dann ist es bereits sortiert und wir geben es zurück.

### Folie 6 — Beispiel

[Folie 6 als PDF](https://inf.zone/download/lectures/3-algorithmen/3.6-merge-sort.pdf#page=6)

```text
MergeSort([5, 2, 1])
├── MergeSort([5]) ✓
└── MergeSort([2, 1])
    ├── MergeSort([2]) ✓
    ├── MergeSort([1]) ✓
    └── Merge([2], [1]) → [1, 2]   ←

Vergleiche: 2 mit 1
Ergebnis: [1, 2]
```

A. Array einelementig? Dann ist es sortiert!

B. Teile Array in zwei Hälften.

C. Rufe Merge Sort auf beiden Hälften auf.

D. Merge die sortierten Hälften.

#### Transkript

*Kein Transkriptabschnitt eindeutig dieser Folie zugeordnet. Möglicherweise eine Aufbau-/Grafikfolie oder eine Abweichung zwischen PDF und Video.*

### Folie 7 — Beispiel

[Folie 7 als PDF](https://inf.zone/download/lectures/3-algorithmen/3.6-merge-sort.pdf#page=7)

```text
MergeSort([5, 2, 1])
├── MergeSort([5]) → [5] ✓
├── MergeSort([2, 1]) → [1, 2] ✓
└── Merge([5], [1, 2]) → [1, 2, 5]   ←

1. Vergleiche: 5 mit 1 → [1]
2. Vergleiche: 5 mit 2 → [1, 2]
3. Übrige Elemente: 5 → [1, 2, 5]
```

A. Array einelementig? Dann ist es sortiert!

B. Teile Array in zwei Hälften.

C. Rufe Merge Sort auf beiden Hälften auf.

D. Merge die sortierten Hälften.

#### Transkript

**[Video 02:04–02:42](https://www.youtube.com/watch?v=ByXjH23FSdw&t=124)**

Falls es nicht einelementig ist, teilen wir es in Schritt B in zwei Hälften.

### Folie 8 — Beispiel

[Folie 8 als PDF](https://inf.zone/download/lectures/3-algorithmen/3.6-merge-sort.pdf#page=8)

```text
MergeSort([5, 2, 1, 3, 6, 4])
├── MergeSort([5, 2, 1]) → [1, 2, 5] ✓
└── MergeSort([3, 6, 4])                  ←
    ├── MergeSort([3])
    └── MergeSort([6, 4])

Linke Hälfte abgeschlossen.
Weiter mit rechter Hälfte.
```

A. Array einelementig? Dann ist es sortiert!

B. Teile Array in zwei Hälften.

C. Rufe Merge Sort auf beiden Hälften auf.

D. Merge die sortierten Hälften.

#### Transkript

**[Video 02:42–03:07](https://www.youtube.com/watch?v=ByXjH23FSdw&t=162)**

In Schritt C, das ist der herrschende Schritt, werden die zwei Hälften getrennt voneinander sortiert. Wissen Sie noch, wie wir ein Array mit Merge Sort sortieren? Genau, mit Merge Sort. Wir rufen uns also rekursiv wieder auf, erst mit der linken Hälfte, dann mit der rechten. Im letzten Schritt haben wir dann zwei sortierte Hälften und die führen wir zusammen. Das ist der Merge-Schritt. Das waren die vier Schritte. Der Schlüssel zum Verständnis ist, wenn sich Merge Sort

**[Video 03:07–03:41](https://www.youtube.com/watch?v=ByXjH23FSdw&t=187)**

in Schritt C selbst aufruft, vertrauen wir darauf, dass die rekursiven Aufrufe korrekt sortierte Teilarrays zurückgeben. Schauen wir uns an, wie unser Array 5 2 1 3 6 4 verarbeitet wird. Im ersten Schritt teilen wir es in die linke Hälfte, also 5 2 1, und in die rechte Hälfte, also 3 6 4. Wir konzentrieren uns zunächst auf die linke Hälfte. Moment mal, wie entscheiden wir eigentlich bei ungerader Länge, wie geteilt wird? Ich frage für die Studierenden. Eine ausgezeichnete Frage. Bei ungerader Länge gibt es keine strenge Vorgabe. Wir treffen einfach eine konsistente Entscheidung.

**[Video 03:41–04:14](https://www.youtube.com/watch?v=ByXjH23FSdw&t=221)**

In diesem Video werden wir immer so aufteilen, dass die linke Hälfte kürzer ist als die rechte. Die rechte bekommt also das übrige Element. Hier haben wir sechs Elemente, also je drei pro Hälfte. Bei der linken Hälfte, das ist fünf, zwei, eins, wiederholen wir das gleiche Prinzip. Wir teilen es in eine neue linke Hälfte, also fünf, und eine neue rechte Hälfte, also zwei, eins auf. Schauen wir uns zuerst wieder die linke Hälfte, also fünf, an.

### Folie 9 — Beispiel

[Folie 9 als PDF](https://inf.zone/download/lectures/3-algorithmen/3.6-merge-sort.pdf#page=9)

```text
MergeSort([3, 6, 4])
├── MergeSort([3]) → [3] ✓
└── MergeSort([6, 4])           ←
    ├── MergeSort([6])
    └── MergeSort([4])

A: Basisfall für [3]? Ja ✓
B: Teilung von [6, 4]
```

A. Array einelementig? Dann ist es sortiert!

B. Teile Array in zwei Hälften.

C. Rufe Merge Sort auf beiden Hälften auf.

D. Merge die sortierten Hälften.

#### Transkript

**[Video 03:41–04:14](https://www.youtube.com/watch?v=ByXjH23FSdw&t=221)**

Das ist unser erster Basisfall. Ein einelementiges Array, das ist ja bereits sortiert, also können wir es direkt an den Aufrufer zurückgeben. Das heißt, wir müssen gar nicht wirklich etwas sortieren.

**[Video 04:14–04:34](https://www.youtube.com/watch?v=ByXjH23FSdw&t=254)**

Bisher nicht. Das ist die Eleganz des Basisfalles. Ein einzelnes Element ist definitionsgemäß sortiert. Aber wir sind ja auch noch gar nicht fertig. Nachdem fünf erledigt ist, widmen wir uns zwei eins. Hier durchlaufen wir wieder unsere vier Schritte. Ist es ein Basisfall? Nein, wir haben zwei Elemente. Also teilen wir in zwei und eins. Beide Teilarrays sind einelementig, also Basisfälle.

**[Video 04:34–05:05](https://www.youtube.com/watch?v=ByXjH23FSdw&t=274)**

Jetzt sind wir beim linken Teil des Arrays ganz unten im Call Stack angekommen und kehren nun aus den Merge Sort Funktionen nach und nach zurück.

### Folie 10 — Beispiel

[Folie 10 als PDF](https://inf.zone/download/lectures/3-algorithmen/3.6-merge-sort.pdf#page=10)

```text
MergeSort([6, 4])
├── MergeSort([6]) → [6] ✓
├── MergeSort([4]) → [4] ✓
└── Merge([6], [4]) → [4, 6]   ←

Vergleiche: 6 mit 4 → [4]
Übrig: 6 → [4, 6]
```

A. Array einelementig? Dann ist es sortiert!

B. Teile Array in zwei Hälften.

C. Rufe Merge Sort auf beiden Hälften auf.

D. Merge die sortierten Hälften.

#### Transkript

*Kein Transkriptabschnitt eindeutig dieser Folie zugeordnet. Möglicherweise eine Aufbau-/Grafikfolie oder eine Abweichung zwischen PDF und Video.*

### Folie 11 — Beispiel

[Folie 11 als PDF](https://inf.zone/download/lectures/3-algorithmen/3.6-merge-sort.pdf#page=11)

```text
MergeSort([3, 6, 4])
├── MergeSort([3]) → [3] ✓
├── MergeSort([6, 4]) → [4, 6] ✓
└── Merge([3], [4, 6]) → [3, 4, 6]    ←

1. Vergleiche: 3 mit 4 → [3]
2. Übrig: [4, 6] → [3, 4, 6]
```

A. Array einelementig? Dann ist es sortiert!

B. Teile Array in zwei Hälften.

C. Rufe Merge Sort auf beiden Hälften auf.

D. Merge die sortierten Hälften.

#### Transkript

> Zuordnung unsicher: wenige gemeinsame Textmerkmale; anhand der benachbarten Folien eingeordnet.

**[Video 04:34–05:05](https://www.youtube.com/watch?v=ByXjH23FSdw&t=274)**

Die Rekursion wickelt sich sozusagen zurück.

### Folie 12 — Beispiel

[Folie 12 als PDF](https://inf.zone/download/lectures/3-algorithmen/3.6-merge-sort.pdf#page=12)

```text
MergeSort([5, 2, 1, 3, 6, 4])
├── [1, 2, 5] ✓
├── [3, 4, 6] ✓
└── Merge([1, 2, 5], [3, 4, 6])    ←

Vergleiche
1 mit 3 → [1]
2 mit 3 → [1, 2]
5 mit 3 → [1, 2, 3]
5 mit 4 → [1, 2, 3, 4]
5 mit 6 → [1, 2, 3, 4, 5]
Rest: 6 → [1, 2, 3, 4, 5, 6]
```

A. Array einelementig? Dann ist es sortiert!

B. Teile Array in zwei Hälften.

C. Rufe Merge Sort auf beiden Hälften auf.

D. Merge die sortierten Hälften.

#### Transkript

**[Video 04:34–05:05](https://www.youtube.com/watch?v=ByXjH23FSdw&t=274)**

Jetzt kommt der spannende Teil: der erste Merge. Bist du bereit? Ja, ich bin mir sicher, unsere Studierenden können es kaum erwarten. Wir haben zwei und eins als sortierte Einheiten und müssen sie zusammenführen. Wir vergleichen dazu die beiden Elemente. Eins ist kleiner als zwei, also kommt eins zuerst. Hä, das sieht ja jetzt nicht besonders spektakulär aus. Ich sehe vor meinen Augen schon viele fragende Gesichter.

**[Video 05:05–05:43](https://www.youtube.com/watch?v=ByXjH23FSdw&t=305)**

Bitte noch kurz durchhalten. Der Schlüssel ist, wir mergeen immer nur bereits sortierte Arrays. In diesem Fall sind es zwar nur einelementige Arrays, aber das Prinzip ist dasselbe. Ein Merge ist wie ein Reißverschluss. Wir führen zwei sortierte Sequenzen zusammen, indem wir immer das kleinere der beiden führenden Elemente nehmen. Ah, der Reißverschlussvergleich. Ich glaube, der ist hilfreich. Das kann man sich gut merken. Jetzt wird es interessant. Wir haben fünf und eins, zwei, beide bereits sortiert. Der Merge-Prozess läuft wieder systematisch und schaut sich die ersten Elemente in den beiden Arrays an. Erst vergleichen wir also die fünf mit der eins, dann die fünf mit der zwei. Da fünf größer ist als beide, wandern dann erst eins und zwei in unser Ergebnisarray.

**[Video 05:43–06:02](https://www.youtube.com/watch?v=ByXjH23FSdw&t=343)**

Danach fügen wir fünf ans Ende. Eine Frage, die mir jetzt gerade so einfällt: Warum speichern wir eigentlich die Zwischenergebnisse? Könnte man nicht? Ah, ich weiß, worauf du hinauswillst. Ob man direkt im ursprünglichen Array arbeiten könnte? Theoretisch ja, aber das würde sehr kompliziert werden. Durch die temporären Arrays behalten wir die Übersicht und vermeiden Fehler.

**[Video 06:02–06:34](https://www.youtube.com/watch?v=ByXjH23FSdw&t=362)**

Es gibt eine In-Place-Version von Merge Sort, die schauen wir uns aber nicht an. Perfekt. Die linke Hälfte ist komplett sortiert. Jetzt wenden wir uns der rechten Hälfte zu. Beachten Sie, wie systematisch der Algorithmus vorgeht. Immer nach dem gleichen Muster. Die rechte Hälfte beginnt genau wie die linke. Drei ist ein Basisfall, also direkt sortiert. Bei sechs, vier müssen wir wieder teilen und Sie ahnen es schon, erhalten zwei Basisfälle. Hier sehen wir wieder einen einfachen Merge. Vier ist kleiner als sechs, also kommt es zuerst. Sechs folgt danach. Jetzt haben wir vier, sechs und müssen es noch mit drei zusammenführen.

**[Video 06:34–07:10](https://www.youtube.com/watch?v=ByXjH23FSdw&t=394)**

Drei ist kleiner als alles in vier sechs, also kommt es zuerst. Da vier sechs bereits sortiert ist, können wir den Rest einfach anhängen. Sollen wir zum finalen Merge der beiden Hälften übergehen? Ja, Zeit wird's. Hey, wo ist denn deine Begeisterung geblieben? Das ist doch wirklich ein tolles Verfahren. Ich könnte den ganzen Tag Merge Sort erklären. Also jetzt kommt der krönende Abschluss. Wir haben zwei perfekt sortierte Hälften: eins zwei fünf und drei vier sechs. Der finale Merge folgt exakt dem gleichen Prinzip wie alle Merges zuvor. Wir vergleichen immer die Anfangselemente und nehmen das kleinere. Das erinnert mich an zwei Kartenspiele.

**[Video 07:10–07:36](https://www.youtube.com/watch?v=ByXjH23FSdw&t=430)**

die ihre sortierten Kartenstapel zusammenmischen.

### Folie 13 — Rekursive Struktur

[Folie 13 als PDF](https://inf.zone/download/lectures/3-algorithmen/3.6-merge-sort.pdf#page=13)

Jeder Aufruf folgt dem gleichen Muster.

Vollständige Bearbeitung der linken Seite vor der rechten.

#### Transkript

**[Video 07:10–07:36](https://www.youtube.com/watch?v=ByXjH23FSdw&t=430)**

Stimmt genau. Wenn wir jetzt den gesamten Prozess betrachten, sehen wir die Eleganz des Algorithmus. Jeder Teilschritt folgt dem gleichen Muster und am Ende fügt sich alles perfekt zusammen. Für das tiefere Verständnis von Merge Sort ist es essentiell, die rekursive Struktur zu durchdringen. Erst wird immer die linke Hälfte vollständig erledigt, dann die rechte und schließlich werden die Ergebnisse zusammengeführt. Es hilft, sich eine detaillierte Schritt-für-Schritt-Liste zu erstellen,

**[Video 07:36–08:09](https://www.youtube.com/watch?v=ByXjH23FSdw&t=456)**

die jeden einzelnen Aufruf und jede Operation dokumentiert. Am besten nummeriert man die Schritte dann hierarchisch durch, damit man immer weiß, wo im Rekursionsbaum man gerade ist. Was unsere Studierenden jetzt wahrscheinlich interessiert: Lohnt sich der ganze Aufwand? Wie effizient ist der Algorithmus?

### Folie 14 — Erstellen einer Schrittliste zum besseren Verständnis

[Folie 14 als PDF](https://inf.zone/download/lectures/3-algorithmen/3.6-merge-sort.pdf#page=14)

Zeichnen Sie den Rekursionsbaum:

- nutzen Sie Einrückungen für die Rekursionstiefe

- markieren Sie Ihren aktuellen Standort im Baum

- nutzen Sie eine hierarchische Nummerierung zur

eindeutigen Bezeichnung der Schritte.

```text
1. MergeSort([5, 2, 1, 3, 6, 4])
   1A: Basisfall-Check
   1B: Teilen in [5, 2, 1] und [3, 6, 4]
   1.1 MergeSort([5, 2, 1])
       1.1A: Basisfall-Check
       1.1B: Teilen in [5] und [2, 1]
       ...
```

#### Transkript

> Zuordnung unsicher: wenige gemeinsame Textmerkmale; anhand der benachbarten Folien eingeordnet.

**[Video 07:36–08:09](https://www.youtube.com/watch?v=ByXjH23FSdw&t=456)**

Das sollten wir uns als nächstes ansehen.

### Folie 15 — Fälle

[Folie 15 als PDF](https://inf.zone/download/lectures/3-algorithmen/3.6-merge-sort.pdf#page=15)

Worst-Case: O(n log n)

Teilung von n Elementen und Rekombination in log n Schritten

Merges: lineare Laufzeitkomplexität

Best-Case: Ω(n log n)

Auch bei bereits sortiertem Array vollständige Durchführung nötig

Vergleich:

Bubble Sort (Worst-Case): O(n²)

Selection Sort (Worst-Case): O(n²)

#### Transkript

**[Video 07:36–08:09](https://www.youtube.com/watch?v=ByXjH23FSdw&t=456)**

Kommen wir zur Analyse der Effizienz von Merge Sort. Während Bubble Sort für jedes Element möglicherweise durch das gesamte Array laufen muss, was zu O von n Quadrat führt, teilt Merge Sort das Problem immer in Hälften. Im Worst-Case-Szenario müssen wir beim Merge Sort n Elemente aufteilen.

**[Video 08:09–08:46](https://www.youtube.com/watch?v=ByXjH23FSdw&t=489)**

und wieder zusammenführen. Diese Teilung führt zu logarithmischer Laufzeitkomplexität. Wir müssen aber auch noch den Aufwand für die Merge-Schritte berücksichtigen. Je länger das Array, desto länger dauert es, die Teilarrays zu mergeen. Insgesamt führt das dann zu einer Gesamtkomplexität von O von n log n. Das ist besser als n². Aber wir brauchen ja auch zusätzlichen Speicherplatz für die temporären Arrays. Es gibt also einen Trade-off zwischen Laufzeit und Speicherplatz. Interessanterweise haben wir im Best-Case, also bei einem bereits sortierten Array, die gleiche Laufzeit. Wir haben also Omega von n log n. Der Algorithmus muss den vollständigen Prozess durchlaufen, auch wenn das Array bereits sortiert ist.

**[Video 08:46–09:03](https://www.youtube.com/watch?v=ByXjH23FSdw&t=526)**

Das unterscheidet Merge Sort von beispielsweise Bubble Sort. Das bedeutet also, dass Merge Sort in vielen Fällen effizienter ist als die simpleren Sortieralgorithmen mit O von n Quadrat. Allerdings zum Preis von höherem Speicherverbrauch.

### Folie 16

[Folie 16 als PDF](https://inf.zone/download/lectures/3-algorithmen/3.6-merge-sort.pdf#page=16)

E X T R A S I N 3 M I N U T E N FRAGEN – ANTWORTEN – RÄTSEL UND KURZE ZUSAMMENFASSUNG

#### Transkript

> Zuordnung unsicher: wenige gemeinsame Textmerkmale; anhand der benachbarten Folien eingeordnet.

**[Video 08:46–09:03](https://www.youtube.com/watch?v=ByXjH23FSdw&t=526)**

Mhm. Ich glaube, das reicht erstmal.

**[Video 09:03–09:35](https://www.youtube.com/watch?v=ByXjH23FSdw&t=543)**

Machen wir noch die drei Extraminuten? Ja klar. In den Extraminuten möchte ich Ihnen heute den kompletten Code für Merge Sort zeigen. Also, wir haben hier die Hauptfunktion Merge Sort, die rekursiv aufgerufen wird, und dann die Merge-Funktion. Moment, Moment, Moment. Ich glaube, so wird das nicht. Die Studierenden schauen garantiert jetzt schon ganz glasig. Lass uns einen Schritt zurückgehen. Kannst du uns stattdessen vielleicht erstmal konzeptionell erklären, wie der Merge-Schritt funktioniert? Das ist doch der Kern des eigentlichen Verfahrens. Ah, natürlich. Du hast völlig recht.

### Folie 17

[Folie 17 als PDF](https://inf.zone/download/lectures/3-algorithmen/3.6-merge-sort.pdf#page=17)

```c
void merge(int arr[], int start, int middle, int end) {
    int i, j, k;
    int n1 = middle - start + 1;
    int n2 = end - middle;
    int L[n1], R[n2];

    for (i = 0; i < n1; i++) L[i] = arr[start + i];
    for (j = 0; j < n2; j++) R[j] = arr[middle + 1 + j];

    i = 0; j = 0; k = start;
    while (i < n1 && j < n2) {
        if (L[i] <= R[j]) {
            arr[k] = L[i];
            i++;
        } else {
            arr[k] = R[j];
            j++;
        }
        k++;
    }
    while (i < n1) {
        arr[k] = L[i];
        i++; k++;
    }
    while (j < n2) {
        arr[k] = R[j];
        j++; k++;
    }
}
```

```c
void mergeSort(int arr[], int start, int end) {
    if (start < end) {
        int middle = start + (end - start - 1) / 2;
        mergeSort(arr, start, middle);
        mergeSort(arr, middle + 1, end);
        merge(arr, start, middle, end);
    }
}
```

#### Transkript

> Zuordnung unsicher: wenige gemeinsame Textmerkmale; anhand der benachbarten Folien eingeordnet.

**[Video 09:03–09:35](https://www.youtube.com/watch?v=ByXjH23FSdw&t=543)**

Lassen wir den Code erstmal beiseite.

### Folie 18 — Der Merge-Algorithmus – Beispiel

[Folie 18 als PDF](https://inf.zone/download/lectures/3-algorithmen/3.6-merge-sort.pdf#page=18)

```text
L: [1, 3, 5, 7]   R: [2, 4, 6]
    ↑                 ↑
    i                 j

A: [ , , , , , , ]
    ↑
    k

Marker:
- i: Position in L
- j: Position in R
- k: Position in A
```

#### Transkript

**[Video 09:35–10:10](https://www.youtube.com/watch?v=ByXjH23FSdw&t=575)**

Schauen wir uns stattdessen an, wie der Merge-Prozess systematisch abläuft. Dafür nehmen wir ein konkretes Beispiel. Der Schlüssel zum Verständnis des Merge-Algorithmus sind die drei Marker i, j und k. Stellen Sie sich diese wie Finger vor, die auf verschiedene Positionen in den Arrays zeigen. In jedem Schritt vergleichen wir die Elemente, auf die i und j zeigen. Das kleinere Element wandert in das Ergebnisarray a an Position k. Dann rücken wir den entsprechenden Marker und k vor. Der wichtige zweite Teil ist das Aufräumen.

### Folie 19 — Der Merge-Algorithmus – Beispiel

[Folie 19 als PDF](https://inf.zone/download/lectures/3-algorithmen/3.6-merge-sort.pdf#page=19)

```text
L: [1, 3, 5, 7]   R: [2, 4, 6]
    ↑                 ↑
    i                 j

A: [ , , , , , , ]
    ↑
    k

Solange i < len(L) UND j < len(R):
    Wenn L[i] ≤ R[j]:
        A[k] = L[i]
        i++
    Sonst:
        A[k] = R[j]
        j++
    k++
```

#### Transkript

> Zuordnung unsicher: wenige gemeinsame Textmerkmale; anhand der benachbarten Folien eingeordnet.

**[Video 09:35–10:10](https://www.youtube.com/watch?v=ByXjH23FSdw&t=575)**

Wenn ein Array leer ist, müssen die restlichen Elemente des anderen Arrays einfach ans Ende kopiert werden.

### Folie 20 — Der Merge-Algorithmus – Beispiel

[Folie 20 als PDF](https://inf.zone/download/lectures/3-algorithmen/3.6-merge-sort.pdf#page=20)

```text
L: [1, 3, 5, 7]   R: [2, 4, 6]
       ↑              ↑
       i              j

A: [1, , , , , , ]
      ↑
      k

Solange i < len(L) UND j < len(R):
    Wenn L[i] ≤ R[j]:
        A[k] = L[i]
        i++
    Sonst:
        A[k] = R[j]
        j++
    k++
```

#### Transkript

> Zuordnung unsicher: wenige gemeinsame Textmerkmale; anhand der benachbarten Folien eingeordnet.

**[Video 10:10–10:32](https://www.youtube.com/watch?v=ByXjH23FSdw&t=610)**

Sie sind ja bereits sortiert.

### Folie 21 — Der Merge-Algorithmus – Beispiel

[Folie 21 als PDF](https://inf.zone/download/lectures/3-algorithmen/3.6-merge-sort.pdf#page=21)

```text
L: [1, 3, 5, 7]   R: [2, 4, 6]
       ↑                 ↑
       i                 j

A: [1,2, , , , , ]
        ↑
        k

Solange i < len(L) UND j < len(R):
    Wenn L[i] ≤ R[j]:
        A[k] = L[i]
        i++
    Sonst:
        A[k] = R[j]
        j++
    k++
```

#### Transkript

> Zuordnung unsicher: wenige gemeinsame Textmerkmale; anhand der benachbarten Folien eingeordnet.

**[Video 10:10–10:32](https://www.youtube.com/watch?v=ByXjH23FSdw&t=610)**

Das heißt, wir brauchen eigentlich drei Schleifen: eine für die Vergleiche und zwei für die möglichen Reste.

### Folie 22 — Der Merge-Algorithmus – Beispiel

[Folie 22 als PDF](https://inf.zone/download/lectures/3-algorithmen/3.6-merge-sort.pdf#page=22)

```text
L: [1, 3, 5, 7]   R: [2, 4, 6]
          ↑              ↑
          i              j

A: [1,2,3, , , , ]
          ↑
          k

Solange i < len(L) UND j < len(R):
    Wenn L[i] ≤ R[j]:
        A[k] = L[i]
        i++
    Sonst:
        A[k] = R[j]
        j++
    k++
```

#### Transkript

> Zuordnung unsicher: wenige gemeinsame Textmerkmale; anhand der benachbarten Folien eingeordnet.

**[Video 10:10–10:32](https://www.youtube.com/watch?v=ByXjH23FSdw&t=610)**

Exakt.

### Folie 23 — Der Merge-Algorithmus – Beispiel

[Folie 23 als PDF](https://inf.zone/download/lectures/3-algorithmen/3.6-merge-sort.pdf#page=23)

```text
L: [1, 3, 5, 7]   R: [2, 4, 6]
          ↑                 ↑
          i                 j

A: [1,2,3,4, , , ]
            ↑
            k

Solange i < len(L) UND j < len(R):
    Wenn L[i] ≤ R[j]:
        A[k] = L[i]
        i++
    Sonst:
        A[k] = R[j]
        j++
    k++
```

#### Transkript

> Zuordnung unsicher: wenige gemeinsame Textmerkmale; anhand der benachbarten Folien eingeordnet.

**[Video 10:10–10:32](https://www.youtube.com/watch?v=ByXjH23FSdw&t=610)**

Genau die haben wir im Code vorhin ja auch gesehen.

### Folie 24 — Der Merge-Algorithmus – Beispiel

[Folie 24 als PDF](https://inf.zone/download/lectures/3-algorithmen/3.6-merge-sort.pdf#page=24)

```text
L: [1, 3, 5, 7]   R: [2, 4, 6]
             ↑              ↑
             i              j

A: [1,2,3,4,5, , ]
              ↑
              k

Solange i < len(L) UND j < len(R):
    Wenn L[i] ≤ R[j]:
        A[k] = L[i]
        i++
    Sonst:
        A[k] = R[j]
        j++
    k++
```

#### Transkript

> Zuordnung unsicher: wenige gemeinsame Textmerkmale; anhand der benachbarten Folien eingeordnet.

**[Video 10:10–10:32](https://www.youtube.com/watch?v=ByXjH23FSdw&t=610)**

Und jetzt wird auch klar, warum.

### Folie 25 — Der Merge-Algorithmus – Beispiel

[Folie 25 als PDF](https://inf.zone/download/lectures/3-algorithmen/3.6-merge-sort.pdf#page=25)

```text
L: [1, 3, 5, 7]   R: [2, 4, 6]
             ↑                 ↑
             i                 j    ←  j == len(R)

A: [1,2,3,4,5,6, ]
                ↑
                k

Solange i < len(L) UND j < len(R):
    Wenn L[i] ≤ R[j]:
        A[k] = L[i]
        i++
    Sonst:
        A[k] = R[j]
        j++
    k++
```

#### Transkript

> Zuordnung unsicher: wenige gemeinsame Textmerkmale; anhand der benachbarten Folien eingeordnet.

**[Video 10:10–10:32](https://www.youtube.com/watch?v=ByXjH23FSdw&t=610)**

Die erste Schleife läuft, solange wir aus beiden Arrays Elemente haben.

### Folie 26 — Der Merge-Algorithmus – Beispiel

[Folie 26 als PDF](https://inf.zone/download/lectures/3-algorithmen/3.6-merge-sort.pdf#page=26)

```text
L: [1, 3, 5, 7]   R: [2, 4, 6]
             ↑                 ↑
             i                 j

A: [1,2,3,4,5,6, ]
                ↑
                k

Fortsetzung des merge-Algorithmus:

Während i < len(L):    Während j < len(R):
    A[k] = L[i]           A[k] = R[j]
    i++                   j++
    k++                   k++
```

#### Transkript

*Kein Transkriptabschnitt eindeutig dieser Folie zugeordnet. Möglicherweise eine Aufbau-/Grafikfolie oder eine Abweichung zwischen PDF und Video.*

### Folie 27 — Der Merge-Algorithmus – Beispiel

[Folie 27 als PDF](https://inf.zone/download/lectures/3-algorithmen/3.6-merge-sort.pdf#page=27)

```text
L: [1, 3, 5, 7]   R: [2, 4, 6]
                ↑              ↑
                i              j

A: [1,2,3,4,5,6,7]
                 ↑
                 k

Fortsetzung des merge-Algorithmus:

Während i < len(L):    Während j < len(R):
    A[k] = L[i]           A[k] = R[j]
    i++                   j++
    k++                   k++
```

#### Transkript

*Kein Transkriptabschnitt eindeutig dieser Folie zugeordnet. Möglicherweise eine Aufbau-/Grafikfolie oder eine Abweichung zwischen PDF und Video.*

### Folie 28 — Der Merge-Algorithmus – Tabelle

[Folie 28 als PDF](https://inf.zone/download/lectures/3-algorithmen/3.6-merge-sort.pdf#page=28)

```text
Schritt   L[i]    R[j]    Aktion      A[k]    Marker (i,j,k)    Verbleibende Elemente
─────────────────────────────────────────────────────────────────────────────────────
  1        1       2      L[i] → A     1      i=1, j=0, k=1     L:[3,5,7], R:[2,4,6]
  2        3       2      R[j] → A     2      i=1, j=1, k=2     L:[3,5,7], R:[4,6]
  3        3       4      L[i] → A     3      i=2, j=1, k=3     L:[5,7], R:[4,6]
  4        5       4      R[j] → A     4      i=2, j=2, k=4     L:[5,7], R:[6]
  5        5       6      L[i] → A     5      i=3, j=2, k=5     L:[7], R:[6]
  6        7       6      R[j] → A     6      i=3, j=3, k=6     L:[7], R:[]
  7        7       -      L[i] → A     7      i=4, k=7          L:[], R:[]
```

#### Transkript

**[Video 10:10–10:32](https://www.youtube.com/watch?v=ByXjH23FSdw&t=610)**

Die anderen beiden kümmern sich um eventuelle Reste. Diese Tabelle zeigt exakt, wie der Algorithmus vorgeht.

**[Video 10:32–11:03](https://www.youtube.com/watch?v=ByXjH23FSdw&t=632)**

In jedem Schritt sehen wir die aktuelle Situation. Welche Elemente werden verglichen? Welches Element wird in das Ergebnisarray geschrieben? Und wie bewegen sich unsere Marker? Ja, da sieht man ganz gut, wie es funktioniert. Besonders interessant ist natürlich der letzte Schritt, wo R dann bereits leer ist. Ja, das ist der Moment, wo die erste Schleife endet und eine unserer Aufräumschleifen übernimmt. In diesem Fall die für die verbleibenden Elemente aus L. Zeichnen Sie sich beim Üben am besten auch so eine Tabelle. Die macht den Ablauf des Algorithmus noch viel transparenter.

### Folie 29 — Merge kombiniert zwei sortierte Arrays

[Folie 29 als PDF](https://inf.zone/download/lectures/3-algorithmen/3.6-merge-sort.pdf#page=29)

Rekursiver Algorithmus:

Teilt Array, sortiert Hälften,

systematisch mit

führt zusammen

drei Markern

„Stabiler“ Algorithmus:

Garantierte Laufzeit

Bewahrt Reihenfolge

O(n log n) in allen Fällen

gleicher Elemente (manchmal wichtig)

Benötigt temporären Speicher in der Größe

Besonders effizient bei

großen Datenmengen und externer Sortierung

des Arrays

> Bildinhalte sind nicht transkribiert; siehe Originalfolie.

#### Transkript

> Zuordnung unsicher: wenige gemeinsame Textmerkmale; anhand der benachbarten Folien eingeordnet.

**[Video 11:03–11:20](https://www.youtube.com/watch?v=ByXjH23FSdw&t=663)**

Damit sind wir dann am Ende unserer heutigen Vorlesung über den Merge Sort, oder? Wie ein Reißverschluss, nur zuverlässiger und mit garantierter Laufzeit. Ja, ich glaube, es reicht für heute. Bis zum nächsten Mal. Dies war Inf-Einf-B.