), mais bon tu fais quand même une traduction assez poussée en remplaçant « on rappelle l'algorithme récursivement » par « on parcourt un arbre » ; en fait tu décides de te placer à un niveau supérieur à celui de l'algorithme que j'ai décrit, d'une certaine façon... enfin je sais pas.
(sinon, ben j'ai pas un tableau, j'ai une liste, donc je peux pas accéder comme ça paf à l'élément d'indice i, je suis bien obligé de parcourir. Mais dans l'implémentation standard ils font pas vraiment le split en fait, ils passent en paramètre le nombre d'éléments à considérer et c'est seulement pour la partie droite qu'ils sont obligés de parcourir la moitié de la liste avant de faire l'appel récursif, par contre la liste n'est jamais coupée en morceaux en fait (il y a juste des pointeurs à des endroits différents de la liste). Ça me semble optimal étant donnée la structure de données, même si je peux me tromper. Bon là je parle de List.sort, après il y a aussi Array.stable_sort sinon mais j'ai la flemme de comprendre comment c'est foutu
)