Mergesort

Datenstrukturen und Algorithmen in Python

Miriam Antona

Software engineer

Mergesort

Nutzt Teile und herrsche
- Teilen
  - zerlegt das Problem in kleinere Teilprobleme
- Lösen
  - Teilprobleme werden rekursiv gelöst
- Zusammenführen
  - Teillösungen werden zur Gesamtlösung kombiniert

Mergesort – in Aktion

Schematische Darstellung einer Liste mit unsortierten Zahlen.

Mergesort – in Aktion

Schematische Darstellung einer Liste mit unsortierten Zahlen. Die Liste wurde in zwei Teile geteilt.

Mergesort – in Aktion

Schematische Darstellung einer Liste mit unsortierten Zahlen. Die Liste wurde in zwei Teile geteilt. Es gibt zwei neue Listen: die linke Hälfte der ursprünglichen Liste und die rechte Hälfte.

Mergesort – in Aktion

Schematische Darstellung einer Liste mit unsortierten Zahlen. Die neuen Listen wurden in zwei Teile geteilt.

Mergesort – in Aktion

Schematische Darstellung einer Liste mit unsortierten Zahlen. Neue Listen entstehen durch weitere Teilungen der zuletzt geteilten Listen.

Mergesort – in Aktion

Schematische Darstellung einer Liste mit unsortierten Zahlen. Die neuen Listen wurden in zwei Teile geteilt.

Mergesort – in Aktion

Schematische Darstellung einer Liste mit unsortierten Zahlen. Neue Listen entstehen durch weitere Teilungen der zuletzt geteilten Listen.

Mergesort – in Aktion

Schematische Darstellung einer Liste mit unsortierten Zahlen. Die neuen Listen wurden in zwei Teile geteilt.

Mergesort – in Aktion

Schematische Darstellung einer Liste mit unsortierten Zahlen. Die neuen Listen wurden in zwei Teile geteilt.

Mergesort – in Aktion

Schematische Darstellung einer Liste mit unsortierten Zahlen. Die Elemente der zuletzt geteilten Listen wurden sortiert.

Mergesort – in Aktion

Schematische Darstellung einer Liste mit unsortierten Zahlen. Die Elemente der zuletzt geteilten Listen wurden zusammengeführt und geordnet.

Mergesort – in Aktion

Schematische Darstellung einer Liste mit unsortierten Zahlen. Die Elemente der zuletzt geteilten Listen wurden zusammengeführt und geordnet.

Mergesort – in Aktion

Schematische Darstellung einer Liste mit unsortierten Zahlen. Die Elemente der zuletzt geteilten Listen wurden zusammengeführt und geordnet. Alle Elemente sind sortiert.

Mergesort – Implementierung

def merge_sort(my_list):
  if len(my_list) > 1:

    mid = len(my_list)//2
    left_half = my_list[:mid]
    right_half = my_list[mid:]

    merge_sort(left_half)
    merge_sort(right_half)


    i = j = k = 0

    while i < len(left_half) and j < len(right_half):

      if left_half[i] < right_half[j]:

        my_list[k] = left_half[i]

        i += 1

      else:

        my_list[k] = right_half[j]

        j += 1

      k += 1

    while i < len(left_half):

      my_list[k] = left_half[i]
      i += 1
      k += 1


    while j < len(right_half):
      my_list[k] = right_half[j]
      j += 1
      k += 1

my_list = [35,22,90,4,50,20,30,40,1]
merge_sort(my_list)
print(my_list)

[1, 4, 20, 22, 30, 35, 40, 50, 90]

Mergesort – Komplexität

Schlechtester Fall: $O(n\log{}n)$
- deutliche Verbesserung gegenüber Bubble-, Auswahl- und Einfügesortierung
- geeignet für große Listen
Durchschnitt: $\Theta(n\log{}n)$
Bester Fall: $\Omega(n\log{}n)$
- andere Algorithmen (z. B. Bubble, Insertionsort) haben besseren Bestfall
Speicher: $O(n)$
- schlechter als Algorithmen mit $O(1)$ Speicher
Varianten reduzieren diesen Speicherbedarf

Lass uns üben!

Datenstrukturen und Algorithmen in Python