Laboratoire Python Interactif

Merge Sort

Le playground s'exécute automatiquement au chargement. Cliquez sur Exécuter mon code pour tracer votre propre Python — chaque étape animée en direct.

Expliquer·Ligne par ligne

Rejouer·Étape par étape

Défi·Indices guidés

XP·...

Pipeline de Flux de Données

advanced Parcours

Bubble Sort

Two Sum

Valid Parentheses

Merge Sort

Quick Sort

Heap Sort

Breadth-First Search

Depth-First Search

Binary Tree Traversal

Fibonacci (Recursive)

Expliquer

Line 1

merge_sort splits array recursively until single elements remain.

Pourquoi cette approche ?

The base case is len(arr) <= 1: a single element is always sorted. This stops the recursion. Without the base case, the function would recurse infinitely.

Structured Explanation

Overview

Le tri fusion divise le tableau en deux moitiés, trie chacune récursivement, puis les fusionne.

Analogy

Comme diviser un jeu de cartes en deux piles, trier chaque pile, puis les fusionner en comparant les cartes du dessus.

Step-by-step

Divise le tableau en deux moitiés
Trie récursivement chaque moitié
Fusionne les deux moitiés triées
Cas de base : tableau de 0 ou 1 élément

Visual

[38,27,43,3,9,82] → [38,27,43] | [3,9,82] → [27,38,43] | [3,9,82] → [3,9,27,38,43,82]

Common mistakes

Oublier le cas de base
Logique de fusion incorrecte — gérer les éléments restants

Practice questions

Implémente le tri fusion et trace les appels récursifs
Utilise le tri fusion pour trier des fichiers qui ne tiennent pas en mémoire

Time

O(n log n)

Space

O(n)

Complexité

Temps

O(n log n)

Espace

O(n)

Aperçu de la Complexité

O(1)

O(log n)temps

O(n)espace

O(n log n)temps

O(n²)

n = 8plage 1-20

POUR N = 8

Complexité	Opérations
O(1)	1
O(log n)	3
O(n)	8
O(n log n)	24
O(n²)	64

Défi

Merge Sort

Indice

Divise, trie récursivement et fusionne — toujours O(n log n).

Studio de Code

Merge Sort

Monaco Prêt

Python Prêt

lesson.pyline 1

Loading editor...

Console de Sortie

0 lines

Pas encore de sortie...

Applications du Monde Réel

Grands jeux de données sur disque (tri externe)

Trier des listes chaînées

Où un tri stable est requis

Comments

Loading comments...

Loading playground…

Complexité

Opérations

O(1)

O(log n)

O(n)

O(n log n)

O(n²)