Vous êtes plusieurs à avoir une fonction merge_sort qui trie correctement, mais qui ne termine pas assez rapidement pour passer les tests. La raison est que sa complexité n'est pas ~nlog
, mais >= n^2.
Le problème est celui indiqué par Simon : il faut une fonction de fusion (merge) efficace, qui fusionne 2 listes en faisant un nombre d'opérations "élémentaires" proportionnel à la somme des longueurs des 2 listes.
Autrement dit, la rapidité du tri fusion vient de la rapidité avec laquelle on peut fusionner 2 listes triées.
Si pour fusionner l1 et l2, vous insérez individuellement chaque élément de l1 dans l2, en oubliant que les 2 listes sont triées, le coût peut valoir
(Taille de l1) x (Taille de l2)
car pour chaque élément de l1, on risque de parcourir toute la liste l2.
C'est le cas par exemple pour l1 = [10; 20; 30] et l2 = [1;2;3;4;5;6;7].
Si le test ne termine pas, vérifiez si la fonction de fusion a bien une complexité linéaire par rapport à la somme de la taille des 2 listes.