Merge sort est un tri divide-and-conquer, stable qui s'exécute en temps garanti O(n log n). Il divise le tableau en deux, trie chaque moitié récursivement, puis fusionne les deux moitiés triées.
Un seul élément est déjà trié (cas de base). Fusionner deux listes triées est linéaire, et nous faisons log n niveaux de fusion.
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]
Idéal quand vous avez besoin de stabilité ou d'une O(n log n) garantie, et pour les linked lists et le tri externe de fichiers énormes. La mémoire O(n) supplémentaire est son principal inconvénient.
Merge sort garantit O(n log n) quel que soit l'entrée, contrairement au O(n²) pire cas du quicksort.
Sa stabilité préserve l'ordre relatif des clés égales, ce qui importe pour le tri multi-clé.
L'étape de fusion est une primitive réutilisable, et la structure divide-and-conquer est un template que vous réutiliserez partout.