Sorting doesn't need any branches. For FHE you need to think like a circuit designer without indexing operations. In that situation your default sort is a sorting network, made out of nlogn conditional swaps.
Once you calculate which value is smaller, the conditional swap itself is trivial. Let's say inputs A and B, comparison result is a boolean C. Outputs X and Y.
Bitwise: X = A&C | B&¬C, Y = A&¬C | B&C
Arithmetic: X = A*C + B*(1-C), Y = A*(1-C) + B*C
Edit: Or to put it another way, one of the most basic things you can make in a circuit is a multiplexer, and a conditional swap is two minimum size multiplexers next to each other.
