Merge sort

Merge sort

Parvis jämförelse, stabil sorteringsalgoritm

Under­klass till	• algoritm  • kombinatorisk algoritm   • sorteringsalgoritm
Upp­täc­ka­re eller upp­fin­na­re	John von Neumann
Upp­täckts­da­tum	1945
Tids­komp­lex­i­tet i värsta fall	$O(n\log n)$
Tids­komp­lex­i­tet i bästa fall	$O(n\log n)$
Tids­komp­lex­i­tet i medel	$O(n\log n)$
Rums­komp­lex­i­tet i värsta fall	$O(n)$
Best-case space comp­lex­i­ty	$O(1)$

Merge Sort är en stabil sorteringsalgoritm. Den sorterar n objekt med tidskomplexitet O (n log n) i värsta fall.

Algoritmen

Merge Sort-algoritmen är av typen söndra och härska, och har konceptuellt följande steg för att sortera en lista med storlek n:

1. Dela upp listan i n lika stora dellistor (alla med längd 1)
2. Slå samman dellistorna parvis i sorterad ordning
3. Upprepa steg två, tills det bara finns en lista kvar

Den slutgiltiga listan är original-listan i sorterad ordning.

Implementering

Nedan följer en rekursiv implementering i Python:

def MergeSort( lista ):
  if len( lista ) == 1:
    return lista

  #Dela listan i två delar
  mitten = len(lista)//2
  lista_1 = MergeSort( lista[0:mitten] )
  lista_2 = MergeSort( lista[mitten:] )

  #Slå samman de sorterade listorna (härska)
  retur_lista = []
  while len( lista_1 ) > 0 and len( lista_2 ) > 0:
    if lista_1[0] < lista_2[0]:
      retur_lista.append( lista_1[0] )
      lista_1.pop(0)
    else:
      retur_lista.append( lista_2[0] )
      lista_2.pop(0)

  #Lägg till de element som "blev över" i slutet
  retur_lista += lista_1
  retur_lista += lista_2
  return retur_lista