Merge sort è un ordinamento divide-and-conquer, stabile che viene eseguito in tempo garantito O(n log n). Divide l'array a metà, ordina ricorsivamente ogni metà, poi unisce le due metà ordinate.
Un singolo elemento è già ordinato (caso base). L'unione di due liste ordinate è lineare, e facciamo log n livelli di unione.
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 quando hai bisogno di stabilità o di O(n log n) garantito, e per liste concatenate e ordinamento esterno di file enormi. La memoria O(n) extra è il suo principale svantaggio.
Merge sort garantisce O(n log n) indipendentemente dall'input, a differenza del caso peggiore O(n²) di quicksort.
La sua stabilità preserva l'ordine relativo delle chiavi uguali, che è importante per l'ordinamento multi-chiave.
Il passo di merge è una primitiva riutilizzabile, e la struttura divide-and-conquer è un template che riutilizzerai ovunque.