Merge sort este un algoritm divide-and-conquer, stabil care funcționează în timp garantat O(n log n). Împarte matricea în jumătate, sortează fiecare jumătate recursiv, apoi fuzionează cele două jumătăți sortate.
Un element singular este deja sortat (caz de bază). Fuzionarea a două liste sortate este liniară, iar noi facem log n niveluri de fuzionare.
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]
Ideal atunci când ai nevoie de stabilitate sau O(n log n) garantat, și pentru liste înlănțuite și sortarea externă a fișierelor enorme. Memoria suplimentară O(n) este principalul dezavantaj.
Merge sort garantează O(n log n) indiferent de intrare, spre deosebire de cazul cel mai rău O(n²) al quicksort.
Stabilitatea acestuia păstrează ordinea relativă a cheilor egale, ceea ce este important pentru sortarea după multiple chei.
Pasul de fuzionare este o primitivă reutilizabilă, iar structura divide-and-conquer este un șablon pe care îl vei refolosi pretutindeni.