Mergesort

Datastructuren en algoritmen in Python

Miriam Antona

Software engineer

Mergesort

Volgt divide and conquer
- Delen
  - splitst het probleem in kleinere subproblemen
- Overwinnen
  - subproblemen worden recursief opgelost
- Combineren
  - oplossingen van subproblemen worden samengevoegd tot de eindsoplossing

Mergesort in actie

Een schematische weergave van een lijst met ongesorteerde nummers.

Mergesort in actie

Een schematische weergave van een lijst met ongesorteerde nummers. De lijst is in tweeën gedeeld.

Mergesort in actie

Een schematische weergave van een lijst met ongesorteerde nummers. De lijst is in tweeën gedeeld. Er zijn twee nieuwe lijsten: de eerste heeft de linkerhelft en de tweede de rechterhelft van de oorspronkelijke lijst.

Mergesort in actie

Een schematische weergave van een lijst met ongesorteerde nummers. De nieuwe lijsten zijn in tweeën gedeeld.

Mergesort in actie

Een schematische weergave van een lijst met ongesorteerde nummers. Er zijn nieuwe lijsten met de opsplitsingen van de laatst gesplitste lijsten.

Mergesort in actie

Een schematische weergave van een lijst met ongesorteerde nummers. De nieuwe lijsten zijn in tweeën gedeeld.

Mergesort in actie

Een schematische weergave van een lijst met ongesorteerde nummers. Er zijn nieuwe lijsten met de opsplitsingen van de laatst gesplitste lijsten.

Mergesort in actie

Een schematische weergave van een lijst met ongesorteerde nummers. De nieuwe lijsten zijn in tweeën gedeeld.

Mergesort in actie

Een schematische weergave van een lijst met ongesorteerde nummers. De nieuwe lijsten zijn in tweeën gedeeld.

Mergesort in actie

Een schematische weergave van een lijst met ongesorteerde nummers. De elementen uit de laatst gesplitste lijsten zijn gesorteerd.

Mergesort in actie

Een schematische weergave van een lijst met ongesorteerde nummers. De elementen uit de laatst gesplitste lijsten zijn samengevoegd en geordend.

Mergesort in actie

Een schematische weergave van een lijst met ongesorteerde nummers. De elementen uit de laatst gesplitste lijsten zijn samengevoegd en geordend.

Mergesort in actie

Een schematische weergave van een lijst met ongesorteerde nummers. De elementen uit de laatst gesplitste lijsten zijn samengevoegd en geordend. Alle elementen zijn gesorteerd.

Mergesort - implementatie

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 - complexiteit

Slechtste geval: $O(n\log{}n)$
- flinke verbetering t.o.v. bubblesort, selection sort en insertion sort
- geschikt voor grote lijsten
Gemiddeld: $\Theta(n\log{}n)$
Beste geval: $\Omega(n\log{}n)$
- andere algoritmen (bijv. bubblesort, insertion sort) hebben een beter best case
Ruimtecomplexiteit: $O(n)$
- slechter dan algoritmen met $O(1)$ ruimte
Varianten verlagen deze ruimtebehoefte

Laten we oefenen!

Datastructuren en algoritmen in Python