L'algorithme Merge Sort, également connu sous le nom de Tri par fusion, est une méthode de tri très efficace, notamment pour les listes chaînées, mais il est également utilisable pour un tableau. Il divise continuellement la liste en deux moitiés, puis fusionne les moitiés triées pour obtenir une liste totalement triée. Son fonctionnement est le suivant:
- Diviser: Le tableau ou la liste non triée est divisé en deux moitiés égales.
- Tri: Chaque moitié est triée de manière récursive.
- Fusion: Les deux moitiés triées sont fusionnées pour obtenir un tableau trié.
Cet algorithme utilise le principe "Diviser pour régner", qui est très efficace avec une complexité temporelle de O(n log n), où n représente le nombre d'éléments dans le tableau ou la liste.
Illustration du tri par fusion:
| Label | Tags | Date |
|---|
| Label | Tags | Date |
|---|
| Label | Tags | Date |
|---|---|---|
| 23. Merge k Sorted Lists | Linked List, Divide and Conquer, Heap (Priority Queue), Merge Sort |
25-03-2024 |