Hippopotame (./7) :
Si a, b, c et d sont les 4 éléments à trier.

Permuter a et b au besoin pour que a<b (I)

De même pour que c<d (II)

De même permuter au besoin a et c pour que a<c (III)

De même pour que b<d (IV)

A ce stade, on sait que a est le plus petit élément et d le plus grand.

Reste à permuter éventuellement b et c pour que b<c. (V)


Ca fait 5 comparaisons et on ne peut pas faire mieux et on peut le démontrer mais flemme.

Application à 4 éléments du tri fusion, si je ne m'abuse .

Sasume (./13) :

Hippopotame (./10) :
Faut toujours s'attendre pour la solution optimale à trouver log(n!)(n le nombre d'éléments à trier ; logarithme en base 2)

Pourquoi ? D'ailleurs je croyais que c'était n*ln(n)

Moi aussi je dirais plutôt que c'est en N*log₂(N)...