A merge sort egy divide-and-conquer, stabil rendezés, amely garantált O(n log n) időben fut. Ketté osztja a tömböt, rekurzívan rendezi mindkét felét, majd összeolvasztja a két rendezett felét.
Egy elem már rendezett (alapesetben). Két rendezett lista összeolvasztása lineáris, és log n szintű összeolvasztást végzünk.
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]
Ideális, amikor stabilitásra vagy garantált O(n log n)-re van szükség, valamint csatolt listákra és hatalmas fájlok külső rendezésére. Az extra O(n) memória a fő hátránya.
A merge sort O(n log n)-t garantál a bemettől függetlenül, ellentétben a quicksort O(n²) legrosszabb esetével.
Annak stabilitása megőrzi az egyenlő kulcsok relatív sorrendjét, amely a többkulcsos rendezéshez fontos.
Az összeolvasztási lépés egy ismételten használható primitív, és a divide-and-conquer szerkezet egy sablon, amelyet mindenhol újra felhasznál.