Merge Sort är en stabil sorteringsalgoritm. Den sorterar n objekt med tidskomplexitet O (n log n) i värsta fall. Att algoritmen är stabil betyder att element med lika värde (exempelvis 7 och 7) hamnar i samma ordning i utdata som de var i indata.
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:
- Dela upp listan i n lika stora dellistor (alla med längd 1)
- Slå samman dellistorna parvis i sorterad ordning
- Upprepa steg två, tills det bara finns en lista kvar
Den slutgiltiga listan är original-listan i sorterad ordning.
Algoritmen har en tidskomplexitet på O(n log n) i värsta fall, vilket är snabbare än exempelvis Quicksort som har en värsta-fallet-tid på O(n2). Nackdelen med Mergesort är utrymmesbehovet då en ny kopia av listan måste skapas för att kunna genomföra alla sammanslagningar. Det innebär att utrymmeskomplexiteten är O(n), jämfört med exempelvis Quicksort vilken klarar sig på O(log n).[1]
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
Referenser
