Quel algorithme de tri a une complexité temporelle en O(n log n) même dans le pire cas et trie presque sans mémoire supplémentaire, comme un tableau de travail ?

Réponse : B. Le tri par tas

Le tri par tas construit un tas binaire dans le tableau, puis échange de façon répétée le maximum situé à la racine avec le dernier élément et réduit le tas : il s'exécute en O(n log n) même dans le pire cas et ne demande qu'une quantité constante de mémoire supplémentaire. Le tri fusion est lui aussi en O(n log n) dans le pire cas, mais sur un tableau il demande une zone de travail proportionnelle à n. Le tri rapide est en O(n log n) en moyenne et rapide en pratique, mais selon le choix du pivot et les données, il peut se dégrader en O(n²). Notez que le tri par tas compare des éléments éloignés, ce qui nuit à son efficacité de cache, et qu'il n'est pas stable non plus.