Tri fusion : diviser, trier, fusionner
Implémentez récursivement le tri fusion, suivez l’arbre diviser pour régner et expliquez pourquoi il garantit une complexité en O(n log n) dans tous les cas.
Tri fusion : diviser, trier, fusionner est une leçon Coding Interview Prep gratuite sur CoddyKit. Ceci est la leçon 2 sur 4. Tu peux lire la leçon complète ci-dessous gratuitement — puis la pratiquer en direct dans le navigateur avec un éditeur de code intégré et un tuteur IA 24/7. Elle fait partie du parcours d'apprentissage Coding Interview Prep, et ta progression se synchronise sur le web et l'application CoddyKit. Le cours Coding Interview Prep comprend 4 leçons au total.
Intuition de la méthode diviser pour régner
Le tri fusion est un algorithme classique de type diviser pour régner : divisez le tableau en deux, triez récursivement chaque moitié, puis fusionnez les deux moitiés triées pour obtenir un seul résultat trié. L’idée essentielle est que fusionner deux tableaux triés s’effectue en O(n), ce qui est bien moins coûteux que de trier depuis le début. Cette décomposition produit un arbre de récursion comportant log n niveaux, chacun nécessitant O(n) opérations de fusion, d’où la borne optimale de O(n log n) pour un tri fondé sur les comparaisons.
# High-level merge sort structure
def merge_sort(arr):
# Base case: 0 or 1 element already sorted
if len(arr) <= 1:
return arr
# Divide
mid = len(arr) // 2
left = merge_sort(arr[:mid]) # sort left half
right = merge_sort(arr[mid:]) # sort right half
# Conquer (merge)
return merge(left, right)
print(merge_sort([38, 27, 43, 3, 9, 82, 10]))
# [3, 9, 10, 27, 38, 43, 82]Explication de l’étape de fusion
Pour fusionner deux tableaux triés, maintenez deux pointeurs, un pour chaque moitié. Comparez les premiers éléments ; copiez le plus petit dans la sortie, puis avancez le pointeur correspondant. Lorsqu’une moitié est épuisée, copiez directement le reste de l’autre moitié. Cette étape s’exécute en O(n) et utilise O(n) d’espace pour le tableau de sortie. L’étape de fusion est le cœur algorithmique du tri fusion : vous devez la comprendre en profondeur.
def merge(left, right):
result = []
i = j = 0
while i < len(left) and j < len(right):
if left[i] <= right[j]: # <= preserves stability
result.append(left[i])
i += 1
else:
result.append(right[j])
j += 1
# Append remaining elements
result.extend(left[i:])
result.extend(right[j:])
return result
print(merge([1,3,5,7], [2,4,6,8]))
# [1, 2, 3, 4, 5, 6, 7, 8]Implémentation complète du tri fusion
Réunir division et fusion : les appels récursifs divisent le problème par deux jusqu'à ce qu'il ne reste que des éléments individuels (déjà triés par définition), puis les appels de fusion les recombinent. À chaque niveau de l'arbre de récursion, les mêmes n éléments au total sont fusionnés (répartis entre plusieurs fusions). La profondeur de récursion est log₂(n), ce qui donne un temps total en O(n log n) et un espace auxiliaire en O(n) pour les tableaux de sortie de la fusion, plus une profondeur de pile d'appels en O(log n).
def merge_sort_full(arr):
if len(arr) <= 1:
return arr
mid = len(arr) // 2
left = merge_sort_full(arr[:mid])
right = merge_sort_full(arr[mid:])
# Merge the two sorted halves
merged = []
i = j = 0
while i < len(left) and j < len(right):
if left[i] <= right[j]: merged.append(left[i]); i += 1
else: merged.append(right[j]); j += 1
merged.extend(left[i:] + right[j:])
return merged
print(merge_sort_full([5,2,4,6,1,3,2,6]))
# [1, 2, 2, 3, 4, 5, 6, 6]Arbre de récursion du tri fusion
Visualisez l'arbre de récursion du tri fusion pour n=8 : le niveau 0 contient un tableau de 8 éléments ; le niveau 1, deux tableaux de 4 ; le niveau 2, quatre tableaux de 2 ; le niveau 3, huit éléments individuels (cas de base). En remontant, le passage du niveau 3→2 fusionne 8 éléments au total, celui du niveau 2→1 en fusionne 8, et celui du niveau 1→0 en fusionne 8. Cela représente 3 niveaux × 8 éléments = 24 opérations ≈ 8 × log₂(8) = 24. Cela confirme O(n log n).
# Trace the tree depth
level_work = []
def merge_sort_traced(arr, depth=0):
if depth >= len(level_work):
level_work.append(0)
if len(arr) <= 1:
return arr
mid = len(arr) // 2
left = merge_sort_traced(arr[:mid], depth+1)
right = merge_sort_traced(arr[mid:], depth+1)
level_work[depth] += len(arr) # track merge work
merged = sorted(left + right) # simplified merge
return merged
merge_sort_traced(list(range(8, 0, -1)))
for d, work in enumerate(level_work):
print(f'Level {d}: {work} elements merged')Tri fusion en place
Le tri fusion récursif standard alloue un espace auxiliaire en O(n) pour la sortie de la fusion. Une version du tri fusion en place existe, mais elle est complexe et ses facteurs constants sont élevés — elle est rarement demandée lors des entretiens. La question complémentaire courante en entretien est la suivante : « Pouvez-vous implémenter le tri fusion avec un espace supplémentaire en O(1) ? » La bonne réponse est : « En théorie, oui, mais les implémentations pratiques sacrifient soit l'espace en O(n), soit la simplicité ; Timsort utilise un espace en O(n) pour les fusions en Python. »
# Bottom-up merge sort: iterative, avoids recursion stack
def merge_sort_bottomup(arr):
n = len(arr)
width = 1
while width < n:
for i in range(0, n, 2 * width):
left = arr[i:i+width]
right = arr[i+width:i+2*width]
# Merge and put back
merged = []
a, b = 0, 0
while a < len(left) and b < len(right):
if left[a] <= right[b]: merged.append(left[a]); a+=1
else: merged.append(right[b]); b+=1
merged += left[a:] + right[b:]
arr[i:i+len(merged)] = merged
width *= 2
return arr
print(merge_sort_bottomup([5,2,4,6,1,3]))
# [1, 2, 3, 4, 5, 6]Le tri fusion est stable
Le tri fusion est stable : les éléments égaux de la moitié gauche apparaissent toujours avant les éléments égaux de la moitié droite dans la sortie fusionnée. Cette garantie vient de l'utilisation de <= (et non de <) lorsqu'on privilégie l'élément de gauche. La stabilité est importante pour le tri à plusieurs clés. En Python, sorted() et list.sort() utilisent Timsort, qui est également stable et s'exécute en O(n log n), ce qui en fait le choix sûr pour tout code de production.
# Demonstrating stability: sort (value, original_index) pairs
items = [(3,'A'), (1,'B'), (3,'C'), (2,'D')]
# Sort by value only
result = merge_sort_full(items) # won't work directly
# Use Python's stable sort:
result = sorted(items, key=lambda x: x[0])
print(result)
# [(1,'B'),(2,'D'),(3,'A'),(3,'C')]
# 'A' comes before 'C' for value=3 (stable order)Fusionner k tableaux triés
Fusionner k tableaux triés contenant au total n éléments peut se faire en fusionnant répétitivement des paires (comme dans un tournoi), en O(n log k). Chaque niveau de fusion traite n éléments, et il y a log k niveaux. Vous pouvez aussi utiliser un tas min de taille k : placez dans le tas le plus petit élément restant de chaque tableau, retirez le minimum, puis ajoutez le suivant de ce tableau. L'approche par tas est également en O(n log k), mais elle utilise moins de mémoire lorsque k est très grand.
import heapq
def merge_k_sorted(arrays):
result = []
heap = []
# Push first element from each array with array index
for i, arr in enumerate(arrays):
if arr:
heapq.heappush(heap, (arr[0], i, 0))
while heap:
val, arr_i, elem_i = heapq.heappop(heap)
result.append(val)
if elem_i + 1 < len(arrays[arr_i]):
next_val = arrays[arr_i][elem_i + 1]
heapq.heappush(heap, (next_val, arr_i, elem_i+1))
return result
arrs = [[1,4,7],[2,5,8],[3,6,9]]
print(merge_k_sorted(arrs)) # [1,2,3,4,5,6,7,8,9]Compter les inversions avec le tri fusion
Compter les inversions (les paires pour lesquelles a[i] > a[j] et i < j) en O(n log n) nécessite une version modifiée du tri fusion. Pendant l'étape de fusion, lorsqu'un élément du sous-tableau de droite est plus petit qu'un élément du sous-tableau de gauche, il forme une inversion avec chaque élément restant dans le sous-tableau de gauche. Ajoutez len(left) - i au compteur à ce moment-là.
def count_inversions(arr):
if len(arr) <= 1:
return arr, 0
mid = len(arr) // 2
left, l_inv = count_inversions(arr[:mid])
right, r_inv = count_inversions(arr[mid:])
merged = []
inversions = l_inv + r_inv
i = j = 0
while i < len(left) and j < len(right):
if left[i] <= right[j]:
merged.append(left[i]); i += 1
else:
merged.append(right[j]); j += 1
inversions += len(left) - i # all remaining left elements > right[j]
merged.extend(left[i:] + right[j:])
return merged, inversions
_, inv = count_inversions([3, 1, 2])
print(inv) # 2: (3,1) and (3,2)Tri fusion ou tri rapide
Le tri fusion garantit O(n log n) dans tous les cas, est stable et constitue le meilleur choix pour les listes chaînées et le tri externe. Le tri rapide a une complexité moyenne en O(n log n), mais un pire cas en O(n²) ; il s'effectue en place (avec un espace de pile en O(log n)) et est souvent plus rapide en pratique grâce à l'efficacité du cache sur les tableaux. La fonction sort intégrée de Python utilise Timsort, une variante du tri fusion : c'est toujours le choix par défaut approprié.
# Head-to-head complexity comparison:
# Algorithm | Best | Avg | Worst | Space | Stable
# Bubble sort | O(n) | O(n^2) | O(n^2) | O(1) | Yes
# Insertion sort| O(n) | O(n^2) | O(n^2) | O(1) | Yes
# Merge sort | O(nlogn)| O(nlogn)| O(nlogn)| O(n) | Yes
# Quick sort | O(nlogn)| O(nlogn)| O(n^2) | O(logn)| No
# Heap sort | O(nlogn)| O(nlogn)| O(nlogn)| O(1) | No
print('Merge sort: stable, O(n log n) guaranteed, O(n) space')Tri externe : le tri fusion à grande échelle
Le tri fusion est l'algorithme à l'origine du tri externe (le tri de données trop volumineuses pour tenir dans la RAM). Les données sont lues par blocs, chaque bloc est trié en mémoire, puis les blocs sont fusionnés depuis le disque. L'étape de fusion lit un élément à la fois dans chaque séquence triée, en ne gardant en mémoire que O(k) éléments simultanément (un par séquence). C'est pourquoi le tri fusion est utilisé dans les bases de données, Hadoop MapReduce et les algorithmes classiques de tri sur bandes.
# Simulated external sort: sort in chunks then merge
def external_sort(data, chunk_size):
chunks = []
for i in range(0, len(data), chunk_size):
chunk = sorted(data[i:i+chunk_size]) # sort in-memory
chunks.append(chunk)
print(f'Created {len(chunks)} sorted chunks')
# Merge all chunks
import heapq
heap = [(c[0], i, 0) for i, c in enumerate(chunks) if c]
heapq.heapify(heap)
result = []
while heap:
val, ci, ei = heapq.heappop(heap)
result.append(val)
if ei + 1 < len(chunks[ci]):
heapq.heappush(heap, (chunks[ci][ei+1], ci, ei+1))
return result
print(external_sort(list(range(20,0,-1)), 5)[:10])Résumé du tri fusion et conseils pour les entretiens
Lors des entretiens, implémenter proprement le tri fusion démontre votre compréhension de la récursion, de l'étape de fusion et de la méthode diviser pour régner. Questions complémentaires courantes :
- Pourquoi O(n log n) et non O(n²) ? (log n niveaux × n opérations par niveau)
- Est-il stable ? (Oui, utilisez <= lors de la fusion)
- Quel espace utilise-t-il ? (O(n) auxiliaire + pile en O(log n))
- Pouvez-vous l'implémenter de manière itérative ? (Oui, avec le tri fusion ascendant)
- Comment l'utiliseriez-vous sur une liste chaînée ? (C'est plus facile que sur un tableau — aucun coût de création d'une tranche en O(n) ; utilisez deux pointeurs, l'un lent et l'autre rapide, pour trouver le point milieu)
# One-shot merge sort for interview clarity:
def ms(a):
if len(a) <= 1: return a
m = len(a) // 2
l, r, res, i, j = ms(a[:m]), ms(a[m:]), [], 0, 0
while i < len(l) and j < len(r):
if l[i] <= r[j]: res.append(l[i]); i+=1
else: res.append(r[j]); j+=1
return res + l[i:] + r[j:]
print(ms([5,2,4,6,1,3])) # [1,2,3,4,5,6]Vérification rapide
Testez votre compréhension des concepts de structures de données et d'algorithmes — préparation aux entretiens de programmation présentés dans cette leçon.
Récapitulatif de la leçon
Dans cette leçon, vous avez appris : le tri fusion divise le tableau au point milieu, trie récursivement chaque moitié et fusionne les deux moitiés triées en O(n), ce qui produit une durée totale d'exécution en O(n log n) sur log n niveaux de récursion, l'étape de fusion utilise <= pour prendre l'élément de gauche en cas d'égalité, ce qui garantit la stabilité, et le tri fusion est l'algorithme à privilégier pour les listes chaînées, le tri externe et les situations où la stabilité est requise — tandis que le tri rapide est préférable pour les tableaux en mémoire lorsque l'espace est limité. Nous allons maintenant implémenter le tri rapide et étudier les stratégies de sélection du pivot.
Questions Fréquemment Posées
La leçon « Tri fusion : diviser, trier, fusionner » est-elle gratuite ?
Oui — le texte complet de « Tri fusion : diviser, trier, fusionner » est gratuit à lire ici sur le web. Pour la pratiquer de manière interactive (un éditeur de code intégré et un tuteur IA 24/7) et déverrouiller le reste du cours Coding Interview Prep, passe à CoddyKit PRO. Le cours Coding Interview Prep comprend 4 leçons au total.
Qu'est-ce que j'apprendrai dans « Tri fusion : diviser, trier, fusionner » ?
Implémentez récursivement le tri fusion, suivez l’arbre diviser pour régner et expliquez pourquoi il garantit une complexité en O(n log n) dans tous les cas. Tu pratiques Coding Interview Prep avec du code pratique que tu exécutes directement dans le navigateur, et un tuteur IA 24/7 répond à tes questions au fur et à mesure que tu avances dans la leçon.
Dois-je avoir de l'expérience pour commencer Coding Interview Prep ?
Aucune expérience préalable n'est requise. Coding Interview Prep sur CoddyKit est structuré pour les débutants jusqu'aux apprenants avancés, donc tu peux commencer ici ou depuis le début et avancer à ton rythme. Ceci est la leçon 2 sur 4.
Combien de temps prend la leçon « Tri fusion : diviser, trier, fusionner » ?
La plupart des leçons CoddyKit prennent environ 5–10 minutes. Chacune est courte et interactive, tu progresses régulièrement et tu repiques exactement où tu t'es arrêté sur le web et l'app.
Peux-tu écrire et exécuter du code dans cette leçon Coding Interview Prep ?
Oui. Chaque leçon Coding Interview Prep inclut un éditeur de code intégré, tu écris et exécutes du vrai code directement dans ton navigateur et tu reçois des retours IA instantanés — aucune configuration locale requise.
Toutes les leçons de ce cours
- Tri à bulles et tri par insertion
- Tri fusion : diviser, trier, fusionner
- Tri rapide et sélection du pivot
- Tris sans comparaison et sort() de Python