Merge sort er en divide-and-conquer, stabil sortering som kjører i garantert O(n log n) tid. Den deler arrayen i to, sorterer hver halvdel rekursivt, og slår så sammen de to sorterte halvdelene.
Et enkelt element er allerede sortert (base case). Sammenslåing av to sorterte lister er lineær, og vi gjør log n nivåer av sammenslåing.
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 trenger stabilitet eller garantert O(n log n), og for linked lists og ekstern sortering av enorme filer. Det ekstra O(n) minne er hovedulempen.
Merge sort garanterer O(n log n) uansett inndata, ulikt quicksort sitt O(n²) worst case.
Stabiliteten bevarer den relative rekkefølgen av like nøkler, noe som er viktig for sortering etter flere nøkler.
Sammenslåingstrinniet er en gjenbrukbar primitiv, og divide-and-conquer strukturen er en mal du vil gjenbruke overalt.