Merge Sort

8.1 Definition von Merge Sort

Merge Sort ist ein effizienter, stabiler und vergleichender Sortieralgorithmus, der den "Teile und Herrsche"-Ansatz nutzt, um Elemente zu sortieren. Der Algorithmus teilt ein Array in zwei Hälften, sortiert rekursiv jede Hälfte und verbindet dann die sortierten Hälften zu einem sortierten Array.

Funktionsprinzip:

Teilung:

• Teile das ursprüngliche Array in der Mitte, um zwei Unterarrays zu erhalten.
• Wiederhole diesen Vorgang für jedes Unterarray, bis jedes Unterarray ein einziges Element (oder leer) ist.

Verschmelzung:

• Verbinde zwei benachbarte Unterarrays zu einem sortierten Array.
• Wiederhole den Verschmelzungsprozess, bis ein sortiertes Array entsteht.

Zeit- und Speicherkomplexität von Merge Sort

Zeitkomplexität:

• Im schlimmsten Fall: O(n log n)
• Im Durchschnittsfall: O(n log n)
• Im besten Fall: O(n log n)

Speicherkomplexität:

O(n) – zusätzlicher Speicher wird benötigt, um temporäre Unterarrays zu speichern.

8.2 Top-Down-Merge-Methode

Die ursprüngliche Sequenz wird rekursiv halbiert, bis wir Teilsequenzen von 1 Element erhalten. Aus den entstandenen Teilsequenzen bilden wir sortierte Paare durch Verschmelzung, dann sortierte Vierer und so weiter.

Schauen wir uns eine Sequenz an:

Wir teilen die Sequenz in 2 Hälften (rekursiv, bis wir Paare erhalten).

Jede Teilsequenz wird durch die Verschmelzungsmethode sortiert und wir erhalten die fertige Sequenz.

8.3 Implementierung des Merge Sort-Algorithmus

Hier kommt die Rekursion ins Spiel! Es ist ein wirklich guter und schneller Algorithmus im Vergleich zu vorherigen. Er teilt das Array in der Mitte, sortiert beide Teile separat und verbindet dann schnell die sortierten Teile.

So sieht die Implementierung ungefähr aus:

def merge_sort(arr):
    if len(arr) > 1:
        mid = len(arr) // 2  # Finden der Mitte des Arrays
        left_half = arr[:mid]  # Teilen des Arrays in zwei Unterarrays
        right_half = arr[mid:]
        
        merge_sort(left_half)  # Rekursives Sortieren der linken Hälfte
        merge_sort(right_half)  # Rekursives Sortieren der rechten Hälfte
        
        i = j = k = 0
        
        # Verschmelzung der sortierten Hälften
        while i < len(left_half) and j < len(right_half):
            if left_half[i] < right_half[j]:
                arr[k] = left_half[i]
                i += 1
            else:
                arr[k] = right_half[j]
                j += 1
            k += 1
        
        # Überprüfung der verbleibenden Elemente
        while i < len(left_half):
            arr[k] = left_half[i]
            i += 1
            k += 1
        
        while j < len(right_half):
            arr[k] = right_half[j]
            j += 1
            k += 1
    return arr

# Beispiel der Anwendung:
arr = [38, 27, 43, 3, 9, 82, 10]
sorted_arr = merge_sort(arr)
print("Sortiertes Array:", sorted_arr)
# Ausgabe: Sortiertes Array: [3, 9, 10, 27, 38, 43, 82]

Der Schlüsselpunkt gleich am Anfang:

def merge_sort(arr):
    if len(arr) > 1:
        mid = len(arr) // 2 # Finden der Mitte des Arrays
        left_half = arr[:mid] # Teilen des Arrays in zwei Unterarrays right_half = arr[mid:]
        
        merge_sort(left_half)  # Rekursives Sortieren der linken Hälfte
        merge_sort(right_half)  # Rekursives Sortieren der rechten Hälfte

Was hier passiert:

1. Wir finden die Mitte des Arrays
2. Teilen das Array in 2 Teile
3. Sortieren jeden Teil separat

Dieser Ansatz beschleunigt den Algorithmus erheblich.