Sorting is not reversible, at least if your output is no larger than your input. [0,1] and [1,0] both sort to [0,1], so you'd already need 1 extra bit to unsort

Sorting is not reversible, at least if your output is no larger than your input. [0,1] and [1,0] both sort to [0,1], so you'd already need 1 extra bit to unsort 2 bits. I don't see how it would help anyway, but maybe I'm misunderstanding your suggestion. The state of these unwanted outputs needs to be kept around, if you know they will be 0 or 1 then the state is already implicit in the machine and the output isn't actually necessary.