Merge sort is een divide-and-conquer, stable sortering die in gegarandeerde O(n log n) tijd loopt. Het splits de array in tweeën, sorteert elke helft recursief, en voegt vervolgens de twee gesorteerde helften samen.
Een enkel element is al gesorteerd (base case). Het samenvoegen van twee gesorteerde lijsten is lineair, en we doen log n niveaus van samenvoeging.
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]
Ideaal wanneer je stabiliteit of gegarandeerde O(n log n) nodig hebt, en voor linked lists en externe sortering van enorme bestanden. Het extra O(n) geheugen is het grootste nadeel.
Merge sort garandeert O(n log n) ongeacht de invoer, in tegenstelling tot het O(n²) worst case van quicksort.
Zijn stabiliteit behoudt de relatieve volgorde van gelijke sleutels, wat belangrijk is voor sorteren op meerdere sleutels.
De merge stap is een herbruikbare primitive, en de divide-and-conquer structuur is een sjabloon die je overal opnieuw zult gebruiken.