fusionner le tri sans mémoire supplémentaire - memory, mergesort

existe-t-il une condition dans laquelle le tri par fusion peut être effectué sans mémoire supplémentaire? mon prof a dit que c'était le cas et qu'il accordera un point bonus à cet égard.

Réponses:

Vous voulez google in place sort sort.

Voici l'un des résultats: http://thomas.baudel.name/Visualisation/VisuTri/inplacestablesort.html

Comme il s’agit d’une question de devoirs, je ne peux que vous indiquer L'art de la programmation informatique. Un bon programmeur devrait pouvoir utiliser les références standard de notre domaine pour rechercher une question telle que celle-ci.

Oui, la réponse à cette question est d'utiliser tri par fusion sur place

Utilisez la liste liée. Cela évitera l’espace supplémentaire O (n) nécessaire lors de la fusion de 2 listes. Cependant, vous ne pouvez rien faire à propos de l'espace occupé par les appels de récursivité, à savoir O (lg (n)).