Diviser pour régner

Diviser pour régner consiste à remplacer un problème par plusieurs sous-problèmes de même nature, mais plus petits. On résout chacun par la même méthode. On combine leurs solutions pour obtenir celle du problème initial. Une simple boucle qui traite les données une à une n’est pas automatiquement une application de cette méthode : il faut identifier le découpage et la combinaison.

Pour trier une liste de n valeurs comparables, on coupe à l’indice n // 2. La partie gauche contient les indices précédant cette coupure, la partie droite contient les autres. Si n est impair, les tailles diffèrent d’une unité. Les listes de longueur zéro ou un sont déjà triées : elles constituent les cas de base. Pour n supérieur à un, chacune des deux parties est strictement plus courte que la liste de départ.

La terminaison vient de cette diminution d’une taille entière positive. On ne peut pas la diminuer indéfiniment : on finit par atteindre un cas de base. Cette justification serait invalide si une des sous-listes gardait toujours la taille initiale. La récursivité exige donc à la fois un arrêt explicite et une progression réelle vers cet arrêt. Un programme qui coupe mal peut boucler même si un cas de base est écrit.

La fusion reçoit deux listes triées par ordre croissant. Elle possède un indice dans chacune et une liste résultat initialement vide. Tant qu’il reste une valeur dans les deux listes, elle compare les valeurs pointées, ajoute la plus petite au résultat et avance seulement l’indice correspondant. Quand une liste est épuisée, elle ajoute toutes les valeurs restantes de l’autre, qui sont déjà dans le bon ordre.

L’invariant utile est le suivant : le résultat contient, dans l’ordre, les valeurs déjà consommées, et aucune valeur encore disponible n’est plus petite que sa dernière valeur. Au départ, le résultat vide respecte cette propriété. À chaque étape, choisir le plus petit des deux éléments de tête conserve l’ordre, car les éléments suivants de chaque liste ne sont pas plus petits. À la fin, toutes les valeurs ont été consommées.

La stabilité signifie que des éléments de même clé gardent leur ordre relatif. Par exemple, deux dossiers ayant la même note conservent leur ordre initial. Le choix de la gauche en cas d’égalité permet cette stabilité si les tris récursifs la préservent aussi. Un tri fusion n’est donc pas stable par son seul nom : cela dépend notamment du traitement des égalités dans son implémentation.

Fusionner deux listes contenant au total n éléments demande de recopier n éléments. Chaque comparaison consomme un élément tant que les deux listes sont non vides. Il y a au plus n − 1 comparaisons de têtes, pour n supérieur ou égal à deux et deux listes non vides. Le coût de fusion est donc linéaire en n. Retirer systématiquement le premier élément avec pop(0) dans une liste Python déplacerait les éléments restants et fausserait cette analyse.

Quand n est une puissance de deux, les divisions créent log₂(n) niveaux jusqu’aux éléments isolés. Sur chaque niveau de fusion, l’ensemble des listes représente n éléments à traiter. Le travail total est ainsi de l’ordre de n × log₂(n). Pour une taille quelconque, les parties restent équilibrées et on conserve le même ordre de grandeur O(n log n) dans le pire cas. Le logarithme indique ici combien de divisions par deux sont nécessaires.

Le tri fusion présenté crée des listes intermédiaires. Son espace auxiliaire maximal simultané est O(n), auquel s’ajoute une pile d’appels de profondeur O(log n), absorbée dans cette borne. Il ne trie pas en place. Le volume cumulé des allocations au cours du temps est une autre mesure : il ne faut pas l’identifier à la mémoire maximale utilisée à un instant donné.

Comparer deux algorithmes demande de fixer ce que l’on mesure : comparaisons, affectations, mémoire ou durée réelle sur une machine. O(n log n) n’est pas une durée en secondes ni un nombre exact d’instructions. Sur de toutes petites listes, les constantes peuvent rendre une méthode plus simple intéressante. Sur des listes presque triées, le coût du tri par insertion dépend du nombre d’inversions ; le mot « presque » ne suffit pas à prouver une borne linéaire.

Une implémentation Python du tri fusion renvoie une copie de la liste lorsque sa longueur est inférieure à deux. Sinon, elle calcule le milieu, trie récursivement les deux tranches et appelle la fonction fusion. Pour la mettre au point, commence par tester fusion seule sur des entrées déjà triées. Tester uniquement le tri complet rend plus difficile l’identification d’une erreur de comparaison ou d’indice.

Un jeu de tests utile contient la liste vide, un seul élément, des doublons, des nombres négatifs, une liste déjà triée, une liste en ordre inverse et une taille impaire. Il faut vérifier l’ordre final, la conservation des valeurs et l’absence de modification de l’entrée si le contrat annonce une nouvelle liste. Comparer le résultat à sorted sur ces données aide à trouver des erreurs ; cela complète, sans remplacer, la justification générale.

La méthode se rencontre aussi dans des traitements d’images ou des calculs sur des structures récursives. Pour reconnaître un nouveau cas, demande-toi si les sous-problèmes sont de même nature, comment ils diminuent et comment leurs résultats se combinent. Le tri rapide est un autre exemple possible, mais ses règles de partition et son coût dépendent du pivot ; il constitue ici un prolongement, pas une étape nécessaire du tri fusion.

Pour poursuivre ton entraînement, ouvre la rubrique S’entraîner du site, à l’adresse /exercices. Reprends d’abord les questions de cette leçon sans afficher les réponses, puis compare ton raisonnement à la correction.