In place sorting of a half edge DS?
My solution to this ended up being not sorting at all. Manipualting an already initialized HE is a nightmare, so instead I built the HE with this property from the get go.
The initialization algorithm is pretty much:

Create a new half edge.
Check if the pair of the half edge exists.
If it exists, you are allocated at index of pair + 1
If it does not exist, increment an offset by 2 and store yourself at offset - 2 (i.e. allocate 2 slots in the edge array and store yourself in the even slot).

Doing it this way before setting next and prev and company guarantees that at any one time the HE is properly initialized.