Non, ce n'est pas possible, même si mon travail serait beaucoup plus facile si c'était le cas :).
Vous avez un facteur O(log n) que vous ne pouvez pas éviter. Vous pouvez choisir de le prendre comme temps ou espace, mais la seule façon de l'éviter est de ne pas trier. Avec un espace O(log n), vous pouvez construire une liste de continuations qui suivent où vous avez caché les éléments qui ne s'adaptent pas tout à fait. Avec la récursivité, cela peut être fait pour tenir dans un tas O(1), mais cela n'est possible qu'en utilisant des trames de pile O(log n).
Voici l'avancée du tri fusion des nombres pairs et impairs de 1 à 9. Remarquez comment vous avez besoin d'un espace log pour suivre les inversions d'ordre causées par les contraintes jumelles d'espace constant et d'échanges linéaires.
. -
135792468
. -
135792468
: .-
125793468
: .-
123795468
#.:-
123495768
:.-
123459768
.:-
123456798
.-
123456789
123456789
Il y a quelques conditions limites délicates, légèrement plus difficiles que la recherche binaire pour les maîtriser, et même dans cette forme (possible), et donc un mauvais problème de devoir; mais un très bon exercice mental.
Mise à jour Apparemment, je me suis trompé et il existe un algorithme qui fournit un temps O(n) et un espace O(1). J'ai téléchargé les articles pour m'éclairer et retire donc cette réponse comme incorrecte.