Merge sort yra dali ir valdyk, stabilus rūšiavimas, kuris garantuotai veikia O(n log n) laiku. Jis padalija masyvą per pusę, rekursyviai rūšiuoja kiekvieną pusę, tada sulieja dvi surūšiuotas puses.
Vienas elementas jau surūšiuotas (bazinis atvejis). Dviejų surūšiuotų sąrašų sujungimas yra tiesinis, ir atliekame log n sujungimo lygius.
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]
Idealu, kai jums reikia stabilumo arba garantuoto O(n log n), taip pat susietų sąrašų ir didelių failų išorinio rūšiavimo. Papildoma O(n) atmintis yra pagrindinis jos trūkumas.
Merge sort garantuoja O(n log n) nepriklausomai nuo įvesties, skirtingai nuo quicksort O(n²) blogiausio atvejo.
Jo stabilumas išsaugo lygių raktų santykinę tvarką, kuri svarbi kelių raktų rūšiavimui.
Sujungimo žingsnis yra pakartotinai naudojamas primitivas, ir dali ir valdyk struktūra yra šablonas, kurį vėl naudosite visur.