Merge sort

Från Wikipedia
Hoppa till navigering Hoppa till sök

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

Algoritmen[redigera | redigera wikitext]

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[redigera | redigera wikitext]

Nedan följer en rekursiv implementering i Python:

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

  #Söndra listan i två delar
  mitten = int( 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