Merge sort je divide-and-conquer, stabilní třídění, které běží v zaručeném O(n log n) čase. Rozdělí pole na půl, rekurzivně setřídí každou polovinu a poté sloučí dvě setříděné poloviny.
Jednotlivý prvek je již setříděn (základní případ). Sloučení dvou setříděných seznamů je lineární, a provádíme log n úrovní sloučení.
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ální, když potřebujete stabilitu nebo zaručený O(n log n), a pro propojené seznamy a externí třídění obrovských souborů. Dodatečná O(n) paměť je jeho hlavní nevýhoda.
Merge sort zaručuje O(n log n) bez ohledu na vstup, na rozdíl od O(n²) nejhoršího případu quicksortu.
Jeho stabilita zachovává relativní pořadí stejných klíčů, což je důležité pro víceklíčové třídění.
Krok sloučení je opakovaně použitelný primitiv, a struktura divide-and-conquer je šablona, kterou budete znovu používat všude.