Si on veut du O(n*log(n)) en pire cas, on peut prendre un heapsort (tri par arbre). En plus, c'est un algo très mignon. On construit un arbre particulier de taille n dont la racine est toujours le plus élément de l'arbre. On extrait cette racine, on la place à la fin du tableau et on recommence avec l'arbre taille n-1. A chaque itération, la réorganisation de l'arbre prend O(log(k)), ceci n fois donne O(n*log(n)).
[^] # PS : Heapsort
Posté par Antoine . En réponse à la dépêche Les promesses de la Native POSIX Threading Library et du prochain Kernel 2.6. Évalué à 6.