Le tri fusion (listes ou tableaux)

Le principe est le suivant :

  • on commence par partager le tableau (ou la liste) en deux parties de longueur à peu près égales
  • on trie récursivement les deux parties
  • on fusionne ces deux parties pour obtenir le tableau (la liste) triée

Remarque : la division en deux parties est simple car on coupe selon la première idée venue (séparation spatiale), mais la fusion est plus délicate (notamment sur les tableaux !).

8.1.1 Tri fusion d'une liste

La fonction split sépare une liste en deux parties de tailles égales (à une unité près)

La fonction merge fusionne deux listes supposées triées dans l’ordre croissant :

La fonction tri_fusion trie récursivement une liste :

Pour voir la suite de ce contenu, vous devez : Pour poursuivre votre exploration, vous pouvez :