Tri Fusion (Merge Sort)
Algorithmique classique
Enonce
Trier une liste par l'algorithme du tri fusion (version récursive). Retourner une nouvelle liste triée.
Signature attendue
def tri_fusion(L: list) -> list:Exemples
tri_fusion([5, 3, 8, 1, 2])→[1, 2, 3, 5, 8]tri_fusion([9, 7, 4, 6])→[4, 6, 7, 9]
📖 Rappel de cours
Diviser pour régner : on coupe la liste en deux, on trie récursivement chaque moitié, puis on fusionne les deux listes triées.
⚠ Le piège : La complexité O(n log n) vient de la profondeur de découpe (log n niveaux) multipliée par le coût d'une fusion complète (n). Savoir le justifier vaut mieux que le réciter.
← Exercices Python pour la prépa — CPGE scientifique et ECG
Exercices du meme theme
- Maximum Récursif
- Conversion Décimal → Binaire
- Tri par Sélection
- Tri Rapide (Quicksort)
- Tri par Comptage (Counting Sort)
- Vérifier si Liste Triée Décroissante
La correction commentee, les indices progressifs, l'execution du code dans le navigateur et la verification par l'IA sont reserves aux abonnes.