Merge sort

Datastrukturer och algoritmer i Python

Miriam Antona

Software engineer

Merge sort

Följer dela och härska
- Dela
  - delar upp problemet i mindre delproblem
- Härska
  - delproblemen löses rekursivt
- Kombinera
  - lösningarna på delproblemen kombineras till en slutlösning

Merge sort – i praktiken

En schematisk representation av en lista med osorterade tal.

Merge sort – i praktiken

En schematisk representation av en lista med osorterade tal. Listan har delats upp i två delar.

Merge sort – i praktiken

En schematisk representation av en lista med osorterade tal. Listan har delats upp i två delar. Det finns två nya listor, den första innehåller den vänstra halvan av den ursprungliga listan och den andra innehåller den högra halvan.

Merge sort – i praktiken

En schematisk representation av en lista med osorterade tal. De nya listorna har delats upp i två delar.

Merge sort – i praktiken

En schematisk representation av en lista med osorterade tal. Det finns nya listor med uppdelningarna av de senast delade listorna.

Merge sort – i praktiken

En schematisk representation av en lista med osorterade tal. De nya listorna har delats upp i två delar.

Merge sort – i praktiken

En schematisk representation av en lista med osorterade tal. Det finns nya listor med uppdelningarna av de senast delade listorna.

Merge sort – i praktiken

En schematisk representation av en lista med osorterade tal. De nya listorna har delats upp i två delar.

Merge sort – i praktiken

En schematisk representation av en lista med osorterade tal. De nya listorna har delats upp i två delar.

Merge sort – i praktiken

En schematisk representation av en lista med osorterade tal. Elementen från de senast delade listorna har sorterats.

Merge sort – i praktiken

En schematisk representation av en lista med osorterade tal. Elementen från de senast delade listorna har slagits ihop och ordnats.

Merge sort – i praktiken

En schematisk representation av en lista med osorterade tal. Elementen från de senast delade listorna har slagits ihop och ordnats.

Merge sort – i praktiken

En schematisk representation av en lista med osorterade tal. Elementen från de senast delade listorna har slagits ihop och ordnats. Alla element är sorterade.

Merge sort – implementation

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]

Merge sort – komplexitet

Värsta fall: $O(n\log{}n)$
- betydande förbättring jämfört med bubbel-, urvals- och insättningssortering
- lämplig för sortering av stora listor
Genomsnittligt fall: $\Theta(n\log{}n)$
Bästa fall: $\Omega(n\log{}n)$
- andra algoritmer (t.ex. bubbel- och insättningssortering) har bättre komplexitet i bästa fall
Platskomplexitet: $O(n)$
- sämre platskomplexitet än algoritmer med $O(1)$
Andra varianter minskar denna platskomplexitet

Nu kör vi en övning!

Datastrukturer och algoritmer i Python