Merge sort je divide-and-conquer, stabilan sort koji radi u garantiranom O(n log n) vremenu. Dijeli niz na pola, rekurzivno sortira svaku polovinu, zatim spaja dvije sortirane polovine.
Jedan element je već sortiran (bazni slučaj). Spajanje dva sortirana popisa je linearno, a mi radimo log n razina spajanja.
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]
Idealno kada trebate stabilnost ili garantirani O(n log n), te za linked liste i vanjsko sortiranje ogromnih datoteka. Dodatna O(n) memorija je njegov glavni nedostatak.
Merge sort garantira O(n log n) bez obzira na ulaz, za razliku od O(n²) najgorg slučaja quicksorta.
Njegova stabilnost čuva relativni redoslijed jednakih ključeva, što je važno za sortiranje s više ključeva.
Korak spajanja je ponovno iskoristivi primitivac, a struktura divide-and-conquer je predložak koji ćete ponovno koristiti svugdje.