Trier par : Diviser, conquérir, combiner

Cette séance de cours couvre le concept de fusion de tri, qui applique la stratégie de division et de conquête au tri. L'instructeur explique le processus de division d'un tableau en deux sous-réseaux, de tri récursivement, puis de fusionnement. La séance de cours se penche sur les détails d'implémentation de l'algorithme de fusion, l'idée de fusion en temps linéaire et l'analyse de la complexité temporelle de Merge Sort. En analysant la relation de récurrence pour Merge Sort, il est montré qu'elle s'exécute dans le temps O (nlog n), ce qui la rend significativement plus rapide que Insertion Sort pour les grandes instances.