CodeUtility
Faciliter la vie des développeurs !
Algorithmes Python

Merge Sort in Python

Split the list in half, sort each half recursively and merge them back: always O(n log n).

  • Intermédiaire
  • 3 min de lecture
  • 1 exemple exécutable
Ce que vous allez apprendre
  • Recursive splitting with slices
  • Merging two sorted lists
  • Time and memory cost
Exécuter dans le compilateur Python →
merge_sort([38, 27, 43, 3]) step by step
  • [3, 27, 38, 43]merged
    • [27, 38]
      • [38]
      • [27]
    • [3, 43]
      • [43]
      • [3]
Split down to single values, then merge sorted pieces on the way back up.

Divide, then merge

Le tri fusion (merge sort) applique la stratégie diviser pour régner (divide and conquer). Il coupe la liste en deux moitiés, trie chacune par un appel récursif, puis fusionne les deux moitiés triées en une liste complète. C'est l'un des algorithmes de tri les plus efficaces et les plus stables.

Points clés

  1. A list of length 0 or 1 is already sorted: that is the base case.
  2. Merge two sorted lists by repeatedly taking the smaller front value.
  3. There are about log n levels of n work each: O(n log n).
  4. It needs O(n) extra memory for the merged lists.

Quand l’utiliser ?

  • Développer votre raisonnement et comprendre étape par étape le fonctionnement d’un algorithme.
  • Choisir la bonne approche quand il faut traiter beaucoup de données ou accélérer un programme.
  • Vous préparer aux examens, aux exercices et aux entretiens de programmation.

Visualisation de Le tri fusion (merge sort) en Python

O(n log n)

Utilisez Lecture ou Étape pour suivre chaque comparaison et déplacement de données.

Code d’exemple

Exécuter le code →
main.py
def merge_sort(values):
    if len(values) <= 1:
        return values
    middle = len(values) // 2
    left = merge_sort(values[:middle])
    right = merge_sort(values[middle:])
    result = []
    left_index = right_index = 0
    while left_index < len(left) and right_index < len(right):
        if left[left_index] <= right[right_index]:
            result.append(left[left_index])
            left_index += 1
        else:
            result.append(right[right_index])
            right_index += 1
    return result + left[left_index:] + right[right_index:]

print(merge_sort([38, 27, 43, 3, 9, 82, 10]))
Obtenir un bouton Run pour cet exemple

Résultat de l’exécution

[3, 9, 10, 27, 38, 43, 82]

Explication du code

La fonction récursive divise la liste jusqu'à ce que chaque morceau n'ait plus qu'un élément, car une liste d'un seul élément est toujours triée. Ensuite, la boucle while fusionne les deux sous-listes en prenant toujours le plus petit des deux éléments de tête. L'algorithme s'exécute toujours en O(n log n) et a besoin de O(n) mémoire supplémentaire.

Modifiez les valeurs et exécutez le programme avec le compilateur Python en ligne CodeUtility, sans installation locale.

Exercices d’approfondissement

Essayez de modifier le code en suivant les pistes ci-dessous. Changer le code et observer le résultat vous fera bien mieux comprendre la leçon que la simple lecture.

  1. Testez avec une liste vide, une liste d’un seul élément et une liste avec des doublons.
  2. Affichez l’état après chaque étape pour observer l’algorithme en action.
  3. Mesurez le temps d’exécution avec 100, 1 000 et 10 000 éléments, puis comparez avec une autre solution.
Exécuter dans le compilateur Python →

S'entraîner avec un défi

Utilisez le contenu de cette leçon pour résoudre un vrai problème. Chaque défi s'exécute dans le navigateur, avec des tests instantanés et une revue par l'IA.

Tous les défis