Drücke "Enter", um den Text zu überspringen.
MergeSort Algorithmus

Merge-Sort

Veröffentlicht 16. März 2025 von Katja Maximini.

Merge-Sort ist ein Sortieralgorithmus, der eine Liste (Array) in kleinere Teillisten aufteilt, diese sortiert und wieder zusammenführt. Den Algorithmus gibt es in zwei Varianten. Beim Top-Down-Merge-Sort wird das Array von oben nach unten nach dem Teile und herrsche(divide and conquer)- Prinzip sortiert. Beim Bottom-Up-Merge-Sort werden Arrays mit einem Elemente iterativ (schrittweise) von unten nach oben zu einer sortierten Gesamtliste zusammengefügt.

Schrittfolge des Algorithmus 

Top-Down-Merge-Sort

Der Algorithmus arbeitet in zwei Phasen. In der ersten Phase teilt er die Ausgangsliste immer mittig in kleinere Teillisten, bis alle Teillisten nur noch ein Element enthalten. Die Mitte des Arrays berechnet man der Formel ⌊ ( left + right ) / 2⌋ ). In der zweiten Phase werden die Elemente der Teillisten paarweise verglichen und schrittweise wieder zusammengeführt (gemergt).

******** Pseudocode MergeSort Top-Down *********

Input: unsorted array A
Output: sorted array A

MergeSort (A, left, right)
  if left < right then
    middle = ⌊ (left + right) / 2⌋ 
    MergeSort (A, left, middle)
    MergeSort (A, middle + 1,right)
  MergeSort()
return A

Bottom-Up-Merge-Sort

Beim Bottom-Up-Merge-Sort gibt es keine Teilungsphase. Der Algorithmus beginnt mit bereits sortierten 1-Element-Arrays und führt diese in aufsteigender Reihenfolge zusammen. Das Merging erfolgt iterativ (schrittweise) von unten nach oben. Dabei  verdoppelt sich in jeder Iteration die Größe der Teilarrays. 

******** Pseudocode MergeSort Botton-Up ********* 

Input: unsorted array A 
Output: sorted array A 

MergeSort (A)
   def size = 1              // Anfangsgröße Teillisten
   def left = 0
   def n = A.length
   while size < n do
      for left = 0 to n mit Schritt 2 ⋅ size do
         middle = left + size - 1          
         right = min(left + 2 ⋅ size - 1, n - 1)      
         MergeSort (A, left, middle, right)  
      size = size ⋅ 2                   
return A

Komplexität des Algorithmus

Best-Case: O(n log2 n), Worst Case: O(n log2 n ),Average Case: O(n log2 n)

Der Merge-Sort-Algorithmus hat bei beiden Varianten eine lineare Speicherplatzkomplexität O(n). In Abhängigkeit von der Anzahl der Elemente der Ausgangsliste benötigt der Merge-Sort immer proportional zusätzlichen Speicher für die Arrays der Teillisten. Beim Bottom-Up-Merge-Sort entfällt der Speicherbedarf für den rekursiven Stack.  Die Laufzeitkomplexität des Merge-Sort-Algorithmus ist in allen drei Fällen quasilinear O(n log2 n), d.h. sie wächst mit zunehmender Eingabegröße etwas mehr als linear. Das Array wird in der Divide-Phase in zwei Hälften geteilt. Die notwendigen Teilungsschritte (Rekursionstiefe) werden mit dem Logarithmus zur Basis 2 ( log2 n ) berechnet, wobei n die Anzahl der Elemente ist. Anschließend werden die Teillisten in den Mergeschritten zusammengeführt.

Beispiel
Der Merge-Sort-Algorithmus teilt ein Array mit vier Elementen  [ 1, 2, 3, 4 ] in vier Arrays mit einem Element [ 1 ] [ 2 ] [ 3 ] [ 4 ]. Die Anzahl der Listenelemente ist n  = 4. Bei einem Array mit vier Elementen benötigt er zwei Teilungen, die Rekursionstiefe beträgt log2 ​4 = 2, da  ⁡22 = 4. In der Conquer-Phase führt der Algorithmus beim Mergen insgesamt fünf Vergleiche durch.

Divide-Phase (Teilungsphase)

Erste Teilung: 
[ 1, 2, 3, 4  ] –> [ 1, 2 ] [ 3, 4 ]
Zweite Teilung:
[ 1, 2 ]  –> [ 1 ] [ 2 ]
[ 3, 4 ]  –> [ 3 ] [ 4 ]

Conquer-Phase (Eroberungsphase)

Erster Merge:  
1. Vergleich [ 1 ] [ 2 ]: 1 < 2       –> [ 1, 2 ] 
2. Vergleich [ 3 ] [ 4 ]: 3 < 4       –> [ 3, 4 ] 

Zweiter Merge:
1. Vergleich [ 1, 2 ] [ 3, 4 ]: 1 < 3    –> [ 1 ]   
2. Vergleich [ 1, 2 ] [ 3, 4 ]: 2 < 3    –> [ 1, 2 ]   
3. Vergleich [ 1, 2 ] [ 3, 4 ]: 3 < 4    –> [ 1, 2, 3 ]   
4. Vergleich [ 1, 2 ] [ 3, 4 ]: Rest 4  –> [ 1, 2, 3, 4 ]   

Beispiel 1:

Merge-Sort-Algorithmus Top-Down im Array A

Der Algorithmus sortiert die acht Zahlen des Arrays A [ 13, 20, 9, 4, 17, 7, 15, 11 ] von oben nach unten in aufsteigender Reihenfolge. Der Algorithmus führt in der Teilungsphase log2 8 = 3 Teilungsschritte durch. Er ermittelt die jeweilige mittlere Position der Arrays mit der Formel ⌊ (left + right) / 2 ⌋ und teilt das Ausgangsarray in acht Arrays mit einem Element. In der Eroberungsphase führt der Algorithmus führt er log 2 ​( 8) = 3 Mergeschritte durch. In jedem Schritt sortiert er das jeweilige Teilarray indem er die aktuellen Elemente mit dem Zwei-Zeiger-Verfahren vergleicht. Abschließend werden die sortierten Teillisten zu einem sortierten Array zusammenfügt.

Initialisierung

Array A [ 13, 20, 9, 4, 17, 7, 15, 11 ], Anzahl Elemente n = 8 
left  = 0
right = A.lenght = 8

Divide-Phase (Teilungsphase)

Erste Teilung:
middle = ⌊ (0 + 8) / 2 ⌋ = 4, A [ 4 ] = 17
Array A [ 13, 20, 9, 4, 17, 7, 15, 11 ]
Teilarray A1 [ 13, 20, 9, 4 ] 
Teilarray A2 [ 17, 7, 15, 11 ] 

Zweite Teilung:
middle = ⌊ (0 + 4) / 2 ⌋ = 2, A1 [ 2 ] = 9, A2 [ 2 ] = 15
Teilarray A1 [ 13, 20, 9, 4 ] , Teilarray A2 [ 17, 7, 15, 11 ] 
Teilarray A1  [ 13, 20 ] 
Teilarray A2  [ 9, 4 ] 
Teilarray A3 [ 17, 7 ] 
Teilarray A4 [ 15, 11 ] 

Dritte Teilung:
middle = ⌊ (0 + 2) / 2⌋ = 1, A11 [ 1 ] = 20, A12 [ 1 ] = 4, A21 [ 1 ] = 7, A22 [ 1 ] = 11
Teilarray A1  [ 13, 20 ] , Teilarray A2  [ 9, 4 ] , Teilarray A3 [ 17, 7 ] , Teilarray A4 [ 15, 11 ] 
Teilarray A1  [ 13 ] 
Teilarray A2  [ 20 ] 
Teilarray A3  [ 9 ] 
Teilarray A4  [ 4 ] 
Teilarray A5 [ 17 ] 
Teilarray A6 [ 7 ] 
Teilarray A7 [ 15 ] 
Teilarray A8 [ 11 ] 

Conquer-Phase (Eroberungsphase) 

Erster Merge:
1. Vergleich A1 [ 13 ],  A2[ 20 ]: 13 < 20 –> A1 [ 13, 20 ]
2. Vergleich A3 [ 9 ],  A4[ 4 ]: 9 > 4  –> A2 [ 4, 9 ]
3. Vergleich A5 [ 7 ],  A6[ 17 ]: 7 <  17 –> A3 [ 7, 17 ]
4. Vergleich A7 [ 15 ],  A8[ 11 ]: 15 > 11 –> A4 [ 11, 15 ]

Zweiter Merge:
1. Vergleich A1 [13, 20 ],  A2[4, 9 ]: 13 > 4 –> A1 [ 4 ]
2. Vergleich A1 [ 13, 20 ],  A2[ 4, 9 ]: 13 > 9 –> A1 [ 4, 9 ]
3. Vergleich A1 [ 13, 20 ],  A2[ 4, 9 ]: 13 < 20 –> A1 [ 4, 9, 13 ]
Rest             A1 [ 13, 20 ],  A2[ 4, 9 ]: 20 = 20  –> A1 [ 4, 9, 13, 20 ]
4. Vergleich A3 [ 7, 17 ],  A4[ 11, 15 ]:   7 < 11 –> A2 [ 7 ]
5. Vergleich A3 [ 7, 17 ],  A4[ 11, 15 ]: 17 > 11 –> A2 [ 7, 11 ]
6. Vergleich A3 [ 7, 17 ],  A4[ 11, 15 ]: 15 < 17 –> A2 [ 7, 11, 15 ]
Rest              A3 [ 7, 17 ],  A4[ 11, 15 ]:  17 = 17 –> A2 [ 7, 11, 15, 17 ]       

Dritter Merge:
1. Vergleich A1 [ 4, 9, 13, 20 ], A2 [ 7, 11, 15, 17 ]: 4 < 7 –> A [ 4 ]
2. Vergleich A1 [ 4, 9, 13, 20 ], A2 [ 7, 11, 15, 17 ]: 4 < 7 –> A [ 4, 7 ]
3. Vergleich A1 [ 4, 9, 13, 20 ], A2 [ 7, 11, 15, 17 ]: 9 < 11 –> A [ 4, 7, 9 ]
4. Vergleich A1 [ 4, 9, 13, 20 ], A2 [ 7, 11, 15, 17 ]: 11 < 13 –> A [ 4, 7, 9, 11 ]
5. Vergleich A1 [ 4, 9, 13, 20 ], A2 [ 7, 11, 15, 17 ]: 13 < 15 –> A [ 4, 7, 9, 11, 13 ]
6. Vergleich A1 [ 4, 9, 13, 20 ], A2 [ 7, 11, 15, 17 ]: 15 < 17  –> A [ 4, 7, 9, 11, 13, 15 ]
7. Vergleich A1 [ 4, 9, 13, 20 ], A2 [ 7, 11, 15, 17 ]: 17 < 20 –> A [ 4, 7, 9, 11, 13, 15, 17 ]
Rest              A1 [ 4, 9, 13, 20 ], A2 [ 7, 11, 15, 17 ]:  20 = 20 –> A [ 4, 7, 9, 11, 13, 15, 17, 20 ]

Output Array A [ 4, 7, 9, 11, 13, 15, 17, 20 ]

Der Algorithmus terminiert nach drei Divide- und Conquer-Phasen und gibt das sortierte Array A [ 4, 7, 9, 11, 13, 15, 17, 20 ] aus. Insgesamt wurden in der Conquer-Phase 4 + 6 + 7 = 17   Vergleiche durchgeführt.

**** Pseudocode MergeSort Top-Down A [13, 20, 9, 4, 17, 7, 15, 11] ****

def A [13, 20, 9, 4, 17, 7, 15, 11]

MergeSort (A, left, right)          
    if left < right then 
         middle = ⌊ (left + right) / 2⌋  
         MergeSort (A, left, middle) 
         MergeSort (A, middle + 1,right) 
      MergeSort () 
return A

Beispiel 2:

Merge-Sort-Algorithmus Bottom-Up für die Arrays A1 bis A8

Der Algorithmus fügt die acht Arrays [ 13 ] [ 20 ] [ 9 ] [ 4 ] [ 17 ]  [ 7 ] [ 15 ] [ 11 ] mit je einem Element (n = 1) von unten nach oben zu einem in aufsteigender Reihenfolge sortierten Array zusammen. Der Algorithmus führt in der Conquer-Phase log2(​8) = 3 Mergeschritte durch. In jedem Schritt vergleicht er die aktuellen Elemente mit dem Zwei-Zeiger-Verfahren und fügt die sortierten Teilarrays schrittweise zu einem sortierten Array zusammen.

Initialisierung
A1 [13]
A2 [20] 
A3 [ 9 ] 
A4 [ 4 ] 
A5 [17] 
A6 [ 7 ] 
A7 [15] 
A8 [11] 
left  = 0
right = A.lenght = 8

Conquer-Phase

Dritter Merge 
1. Vergleich A1 [ 4, 9, 13, 20 ], A2 [ 7, 11, 15, 17 ]: 4 < 7 –> A [ 4, 7 ]
2. Vergleich  [ 4, 9, 13, 20 ], [ 7, 11, 15, 17 ]: 7 < 9  –> A [ 4, 7, 9 ] 
3. Vergleich  [ 4, 9, 13, 20 ], [ 7, 11, 15, 17 ]: 9 < 11 –> A [ 4, 7, 9, 11 ]
4. Vergleich  [ 4, 9, 13, 20 ], [ 7, 11, 15, 17 ]: 11 < 13  –> A [ 4, 7, 9, 11, 13 ]
5. Vergleich  [ 4, 9, 13, 20 ], [ 7, 11, 15, 17 ]: 13 < 15  –> A [ 4, 7, 9, 11, 13, 15 ]
6. Vergleich  [ 4, 9, 13, 20 ], [ 7, 11, 15, 17 ]:13 < 17 –> A [ 4, 7, 9, 11, 13, 15, 17 ]
7. Vergleich  [ 4, 9, 13, 20 ], [ 7, 11, 15, 17 ]: 20 > 17 –> A [ 4, 7, 9, 11, 13, 15, 17, 20 ]

Zweiter Merge 
1. Vergleich A1 [ 13, 20 ],  A2[ 4, 9 ]:13 > 4  –> A1 [ 4, 13 ]
2. Vergleich A1 [ 13, 20 ],  A2[ 4, 9 ]:13 > 9  –> A1 [ 4, 9, 13 ]
3. Vergleich A1 [ 13, 20 ],  A2[ 4, 9 ]:20 > 9  –> A1 [ 4, 9, 13, 20 ]
4. Vergleich A3 [ 7, 17 ], A4 [ 11, 15 ]: 7 < 11  –> A2 [ 7, 11 ]
5. Vergleich A3 [ 7, 17 ], A4 [ 11, 15 ]: 7 < 15  –> A2 [ 7, 11, 15 ]
6. Vergleich A3 [ 7, 17 ], A4 [ 11, 15 ]: 17 > 15  –> A2 [ 7, 11, 15, 17 ]

Erster Merge 
1. Vergleich A1 [ 13 ],  A2 [ 20 ]:13 < 20 –> A1 [ 13, 20 ]
2. Vergleich A3 [ 9 ], A4 [ 4 ]: 9 > 4  –> A2 [ 4, 9 ]
3. Vergleich A5 [ 17 ], A6 [ 7 ]:17 > 7 –> A3 [ 7, 17 ]
4. Vergleich A7 [ 15 ], A8 [ 11 ]: 15 > 11 –> A4 [ 11, 15 ]    

Output: Array A [ 4, 7, 9, 11, 13, 15, 17, 20 ]

Der Algorithmus terminiert nach drei Divide- und drei Conquer-Phasen und gibt das sortierte Array A [ 4, 7, 9, 11, 13, 15, 17, 20 ]  aus. Insgesamt hat er 7 + 6 + 4 = 17 Vergleiche vorgenommen.

******** Pseudocode MergeSort Botton-Up ********* 

Input: 
A1 [13]
A2 [20]
A3 [9]
A4 [4]
A5 [17]
A6 [7]
A7 [15]
A8 [11]

MergeSort (A1,A2,A3,A4,A5,A6,A7,A8)
   def size = 1              
   def left = 0
   def n = A.length
   while size < n do
      for left = 0 to n mit Schritt 2 ⋅ size do
         middle = left + size - 1          
         right = min(left + 2 ⋅ size - 1, n - 1)      
         MergeSort (A, left, middle, right)  
      size = size ⋅ 2                   
return A

Published in Algorithmen and Informatik

Die Kommentarfunktion ist deaktiviert, aber Trackbacks und Dingbacks sind offen.