Merge sort je deli-in-vladaj, stabilno sortiranje, ki deluje v O(n log n) času. Razcepi polje na polovico, vsako polovico rekurzivno sortira, nato pa skupaj zlepi dve sortirani polovici.
En sam element je že sortiran (osnovni primer). Zlivanje dveh sortiranih seznamov je linearno in izvedemo log n nivojev zlivanja.
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, ko potrebuješ stabilnost ali zagotovljen O(n log n), in za povezane sezname in zunanje sortiranje velikanskih datotek. Dodatna O(n) pomnilnika je njegova glavna pomanjkljivost.
Merge sort zagotavlja O(n log n) ne glede na vhod, za razliko od O(n²) najslabšega primera quicksorta.
Njegova stabilnost ohrani relativni vrstni red enakih ključev, kar je pomembno za sortiranje z več ključi.
Korak zlivanja je ponovno uporabljiva primitiva in struktura deli-in-vladaj je predloga, ki jo boš ponovno uporabil povsod.