Sally
: 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.

Ben oui exactement, c'est ce que j'ai dit

(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 )

Oui, évidemment avec une structure pourrie comme une liste on peut pas faire de miracle (et encore j'ai pas parlé des problèmes de localité mémoire ou d'overhead lié au fait que chaque élément est muni d'un pointeur ), mais si Caml choisit la liste comme structure de donnée principale c'est bien parce que c'est facile d'y accéder récursivement en bas niveau... Alors que si on se place à plus haut niveau ce besoin disparaît