Merge sort er en divide-and-conquer, stabil sortering, der kører i garanteret O(n log n) tid. Den deler arrayet i halvdele, sorterer hver halvdel rekursivt og fusionerer derefter de to sorterede halvdele.
Et enkelt element er allerede sorteret (basistilfælde). Fusionering af to sorterede lister er lineær, og vi udfører log n niveauer af fusionering.
def merge_sort(arr):
if len(arr) <= 1:
return arr
mid = len(arr) // 2
left = merge_sort(arr[:mid]) # sort left half
right = merge_sort(arr[mid:]) # sort right half
return merge(left, right)
def merge(a, b):
result, i, j = [], 0, 0
while i < len(a) and j < len(b):
if a[i] <= b[j]: # <= keeps it stable
result.append(a[i]); i += 1
else:
result.append(b[j]); j += 1
result.extend(a[i:]); result.extend(b[j:])
return result
merge_sort([5, 2, 4, 1, 3]) # -> [1, 2, 3, 4, 5]
Ideelt når du har brug for stabilitet eller garanteret O(n log n), og til linkede lister og ekstern sortering af enorme filer. Den ekstra O(n) hukommelse er dens største ulempe.
Merge sort garanterer O(n log n) uanset input, i modsætning til quicksorts O(n²) værste tilfælde.
Dens stabilitet bevarer den relative rækkefølge af lige nøgler, hvilket betyder noget for sortering med flere nøgler.
Fusioneringstrinet er en genanvendelig primitiv, og divide-and-conquer-strukturen er en skabelon, du vil genbruge overalt.