Merge Sort
Dernière mise à jour
Le tri fusion est un algorithme de type diviser pour régner. Il divise récursivement le tableau en deux jusqu'à ce que chaque morceau ne contienne qu'un seul élément (trivialement trié), puis fusionne les morceaux dans l'ordre. L'étape de fusion parcourt deux sous-tableaux triés avec deux pointeurs, en copiant toujours le plus petit élément de tête. Appuyez sur lecture ci-dessus pour voir le tableau se reconstruire fusion après fusion.
Comme il divise toujours en deux, le tri fusion s'exécute en temps O(n log n) dans tous les cas : son pire cas est aussi bon que son meilleur cas. En contrepartie, il utilise O(n) d'espace supplémentaire pour le tampon de fusion temporaire.
Complexité en temps et en espace
| Cas | Complexité | Remarques |
|---|---|---|
| Meilleur cas | O(n log n) | Divise toujours l'entrée en deux |
| Cas moyen | O(n log n) | Ordre aléatoire |
| Pire cas | O(n log n) | Garanti - aucune mauvaise entrée |
| Espace | O(n) | Tampon temporaire pour la fusion |
| Stable | Oui | Égalités résolues par la gauche lors de la fusion |
Étape par étape
| Étape | Ce qui se passe |
|---|---|
| 1 | Si la plage a 0 ou 1 élément, elle est déjà triée. |
| 2 | Divise la plage en deux moitiés. |
| 3 | Trie récursivement la moitié gauche par tri fusion. |
| 4 | Trie récursivement la moitié droite par tri fusion. |
| 5 | Fusionne les deux moitiés triées avec deux pointeurs. |
Exemple détaillé
Tri de [5, 2, 4, 1] :
| Passe | Tableau | Action |
|---|---|---|
| Diviser | [5, 2] | [4, 1] | Divise le tableau en deux moitiés |
| Diviser | [5] [2] | [4] [1] | Divise encore jusqu'à ce que chaque morceau soit un seul élément |
| Fusionner | [2, 5] | [1, 4] | Fusionne [5],[2] en [2, 5] et [4],[1] en [1, 4] |
| Fusionner | [1, 2, 4, 5] | Fusionne [2, 5] et [1, 4] : choisit 1, puis 2, puis 4, puis 5 |
| Terminé | [1, 2, 4, 5] | Le tableau est entièrement trié |
Quand utiliser le tri fusion
| À utiliser quand | À éviter quand |
|---|---|
Vous avez besoin d'un pire cas garanti en O(n log n) | La mémoire est limitée et O(n) d'espace supplémentaire est inacceptable |
| La stabilité compte (les clés égales gardent leur ordre) | Vous triez de petits tableaux où le tri par insertion est plus rapide |
| Vous triez une liste chaînée | Le tri en place est une exigence stricte |
| Les données sont trop grandes pour la RAM (tri externe) | La localité de cache domine et les passes en place de quicksort gagnent |
Code de Merge Sort
Une implémentation propre et exécutable de Merge Sort en Python, JavaScript, Java, C++, C. Choisissez un langage, copiez le code ou ouvrez-le préchargé dans le Playground Coddy.
Code de Merge Sort en Python
Python
1def merge_sort(a):2 if len(a) <= 1:3 return a4 mid = len(a) // 25 left = merge_sort(a[:mid])6 right = merge_sort(a[mid:])7 return merge(left, right)8
9
10def merge(left, right):11 out = []12 i = j = 013 while i < len(left) and j < len(right):14 if left[i] <= right[j]:15 out.append(left[i])16 i += 117 else:18 out.append(right[j])19 j += 120 out.extend(left[i:])21 out.extend(right[j:])22 return out23
24
25nums = [38, 27, 43, 3, 9, 82, 10]26print("Before:", nums)27print("After: ", merge_sort(nums))Code de Merge Sort en JavaScript
JavaScript
1function mergeSort(arr) {2 if (arr.length <= 1) return arr;3 const mid = Math.floor(arr.length / 2);4 const left = mergeSort(arr.slice(0, mid));5 const right = mergeSort(arr.slice(mid));6 return merge(left, right);7}8
9// Merge two sorted arrays into one sorted array10function merge(left, right) {11 const out = [];12 let i = 0;13 let j = 0;14 while (i < left.length && j < right.length) {15 out.push(left[i] <= right[j] ? left[i++] : right[j++]);16 }17 return out.concat(left.slice(i), right.slice(j));18}19
20const data = [5, 2, 9, 1, 7, 3];21console.log("Before:", data);22console.log("Sorted:", mergeSort(data));Code de Merge Sort en Java
Java
1import java.util.Arrays;2
3public class Main {4 static void mergeSort(int[] arr, int left, int right) {5 if (left >= right) return;6 int mid = (left + right) / 2;7 mergeSort(arr, left, mid);8 mergeSort(arr, mid + 1, right);9 merge(arr, left, mid, right);10 }11
12 // Merge two sorted halves into a temp array, then copy back13 static void merge(int[] arr, int left, int mid, int right) {14 int[] tmp = new int[right - left + 1];15 int i = left, j = mid + 1, k = 0;16 while (i <= mid && j <= right) {17 tmp[k++] = arr[i] <= arr[j] ? arr[i++] : arr[j++];18 }19 while (i <= mid) tmp[k++] = arr[i++];20 while (j <= right) tmp[k++] = arr[j++];21 System.arraycopy(tmp, 0, arr, left, tmp.length);22 }23
24 public static void main(String[] args) {25 int[] arr = {38, 27, 43, 3, 9, 82, 10};26 System.out.println("Before: " + Arrays.toString(arr));27 mergeSort(arr, 0, arr.length - 1);28 System.out.println("After: " + Arrays.toString(arr));29 }30}Code de Merge Sort en C++
C++
1#include <iostream>2#include <vector>3
4void printVec(const std::vector<int>& a) {5 for (int x : a) std::cout << x << " ";6 std::cout << "\n";7}8
9void merge(std::vector<int>& a, int lo, int mid, int hi) {10 std::vector<int> tmp;11 tmp.reserve(hi - lo + 1);12 int i = lo, j = mid + 1;13 while (i <= mid && j <= hi) {14 if (a[i] <= a[j]) tmp.push_back(a[i++]);15 else tmp.push_back(a[j++]);16 }17 while (i <= mid) tmp.push_back(a[i++]);18 while (j <= hi) tmp.push_back(a[j++]);19 for (size_t k = 0; k < tmp.size(); ++k) a[lo + k] = tmp[k];20}21
22void mergeSort(std::vector<int>& a, int lo, int hi) {23 if (lo >= hi) return;24 int mid = lo + (hi - lo) / 2;25 mergeSort(a, lo, mid); // sort the left half26 mergeSort(a, mid + 1, hi); // sort the right half27 merge(a, lo, mid, hi); // merge the sorted halves28}29
30int main() {31 std::vector<int> data = {38, 27, 43, 3, 9, 82, 10};32 std::cout << "Before: ";33 printVec(data);34 mergeSort(data, 0, static_cast<int>(data.size()) - 1);35 std::cout << "After: ";36 printVec(data);37 return 0;38}Code de Merge Sort en C
C
1#include <stdio.h>2#include <stdlib.h>3
4void printArr(const int a[], int n) {5 for (int i = 0; i < n; i++) printf("%d ", a[i]);6 printf("\n");7}8
9void merge(int a[], int lo, int mid, int hi) {10 int* tmp = malloc((hi - lo + 1) * sizeof(int));11 int i = lo, j = mid + 1, k = 0;12 while (i <= mid && j <= hi) {13 if (a[i] <= a[j]) tmp[k++] = a[i++];14 else tmp[k++] = a[j++];15 }16 while (i <= mid) tmp[k++] = a[i++];17 while (j <= hi) tmp[k++] = a[j++];18 for (k = 0; k <= hi - lo; k++) a[lo + k] = tmp[k];19 free(tmp);20}21
22void mergeSort(int a[], int lo, int hi) {23 if (lo >= hi) return;24 int mid = lo + (hi - lo) / 2;25 mergeSort(a, lo, mid); // sort the left half26 mergeSort(a, mid + 1, hi); // sort the right half27 merge(a, lo, mid, hi); // merge the sorted halves28}29
30int main(void) {31 int data[] = {38, 27, 43, 3, 9, 82, 10};32 int n = sizeof(data) / sizeof(data[0]);33 printf("Before: ");34 printArr(data, n);35 mergeSort(data, 0, n - 1);36 printf("After: ");37 printArr(data, n);38 return 0;39}FAQ sur le tri fusion
Quelle est la complexité temporelle du tri fusion ?
Le tri fusion est en
O(n log n) dans le meilleur, le pire et le cas moyen, car il divise toujours le tableau en deux. Il utilise O(n) d'espace supplémentaire pour le tampon de fusion.Le tri fusion est-il stable ?
Oui, lorsque l'étape de fusion résout les égalités en prenant d'abord dans la moitié gauche. Cela conserve les éléments égaux dans leur ordre relatif d'origine, c'est pourquoi le tri fusion est un choix courant pour le tri stable.
Pourquoi utiliser le tri fusion plutôt que quicksort ?
Le tri fusion garantit
O(n log n) même sur des entrées adverses et est stable, alors que quicksort peut se dégrader en O(n²). Le tri fusion est aussi préféré pour les listes chaînées et le tri externe. L'inconvénient est sa mémoire supplémentaire en O(n).Quelle est la différence entre le tri fusion et quicksort ?
Les deux sont des tris de type diviser pour régner, mais quicksort partitionne autour d'un pivot et trie en place avec
O(log n) d'espace de pile, tandis que le tri fusion divise aveuglément en deux et fusionne avec un tampon en O(n). Quicksort est généralement plus rapide en pratique grâce à la localité de cache, mais le tri fusion a un pire cas garanti en O(n log n) et est stable.Quand devrais-je utiliser le tri fusion en pratique ?
Optez pour le tri fusion quand vous avez besoin d'un tri stable avec une borne garantie en
O(n log n), pour trier des listes chaînées (où il n'a pas besoin d'accès aléatoire), ou pour le tri externe de données trop volumineuses pour la mémoire. Évitez-le quand la mémoire est rare, car il nécessite O(n) d'espace supplémentaire.Le tri fusion trie-t-il en place ?
Non. Le tri fusion standard alloue un tampon temporaire en
O(n) pour fusionner les deux moitiés, il n'est donc pas en place. Des variantes de fusion en place existent, mais elles sont complexes et soit plus lentes soit perdent la stabilité, donc la version à tampon reste le choix courant.Ressources associées
Plus de visualisations
