Merge sort është një renditje përça-dhe-sundo, stabile që funksionon në kohë të garantuar O(n log n). Ajo ndan array-in në gjysma, rendit secilën gjysme në mënyrë rekurzive, më pas bashkon dy gjysmat e renditura.
Një element i vetëm është tashmë i renditur (rasti bazë). Bashkimi i dy listave të renditura është linear, dhe ne bëjmë log n nivele bashkimi.
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]
Ideale kur ke nevojë për qëndrueshmëri ose garantim O(n log n), dhe për lista të lidhura dhe renditje të jashtme të skedarëve masivë. Memorja shtesë O(n) është e meti kryesor.
Merge sort garanton O(n log n) pavarësisht nga hyrja, ndryshe nga rasti më i keq O(n²) i quicksort-it.
Qëndrueshmëria e tij ruan rendin relativ të çelësave të barabartë, çka është e rëndësishme për renditjen me shumë çelësa.
Hapi i bashkimit është një primitiv i rizbatueshem, dhe struktura përça-dhe-sundo është një shabllon që do ta ripërdorësh kudo.