---

Dans ce chapitre, nous allons étudier certains algorithmes dont la philosophie de fonctionnement se rapproche de l’adage “diviser pour régner” . L’idée est de décomposer un problème en plusieurs sous-problèmes, que l’on résoudra suivant le même principe. Il ne reste plus alors qu’à combiner les résultats des sous-problèmes pour obtenir la réponse recherchée.

Nous reviendrons dans un premier temps sur la recherche dichotomique normalement déjà étudiée en Première, puis nous la réexaminerons en utilisant la récursivité étudiée en Terminale.

Dans un second temps, nous découvrirons un nouvel algorithme de tri appelé le tri fusion. Cet algorithme est un exemple parfait du principe “diviser pour régner”. Par rapport aux algorithmes de tri par insertion ou par sélection étudiés en Première, son efficacité est bien meilleure: elle est même optimale !