Bonjour,
Essayez de penser à une preuve par récurrence que la fonction merge_sort est correcte, par récurence sur la taille de son parametre :
Cas de base : Les listes de longueur 0 et 1 sont triées [Check]
hypothèse : merge_sort sait trier toutes les listes de longueur comprises entre 0 et m.
hérédité : on a une liste ln de taille n, on la découpe en deux listes lk1 et lk2, telle que leur longueur vérifient : n = k1 + k2 (k1 et k2 différents de 0 et inférieur à m). Par hypothèse de récurrence, on sait trier les listes de lk1 et lk2. merge sait prendre deux listes triés et les fusionner de sorte que le résultat soit trié, et donc merge_sort sait trier une liste de taille n. [check]
(il manque quelques arguments pour en faire une preuve complète, mais l'idée est là).
Dit autrement : la magie c'est que merge_sort, par hypothèse, sait trier des listes plus petites que son paramètre. L'idée de l'algo, c'est donc de prendre son paramètre, de construire deux listes plus petites qu'elle saura trié, et de combiner ces listes triées pour retourner son paramètre trié.