If we have an state $\alpha|abc\rangle + \beta|bad\rangle$, and we know that $a<b$, how can we obtain state $\alpha|abc\rangle + \beta|abd\rangle$ without entangled ancillas, if we don't know $c$ or $d$?
With an ancilla it is simple: just use it for comparison purposes and controlled on it, swap the first and second register. But then we cannot uncompute it.
There's no way to do that. It would violate reversibility.
What you can do, from a larger scale algorithm design perspective, is make sure the state you're operating on is a state where this is not a problem. For example, if the state is invariant under permutation, sorting it will produce comparison state qubits that are separable from the sorted item qubits. "Improved techniques for preparing eigenstates of fermionic Hamiltonians" uses sorting networks on states with that property (or exponentially close approximations of that property, rather).
