Not necessarily. A branch-free algorithm can totally have a data dependency from the previous iteration of the loop to the next, making it impossible to vectorize.
That's true, although there are sometimes workarounds for that by modifying the algorithm to iterate over a small groups where there is still a data-dependency between iterations, but not within each group, allowing one to use SIMD. e.g. instead of delta compression over an array of integers where you subtract each integer from the prior one, you can subtract each group from the prior one with only a small loss of compression ratio.
The question is, is there such a dependency in this algorithm? I didn't check.
Yes, sorting typically (and this one specifically) has long dependency chains. The natural reflex is to split the chains across multiple workers... and that's how you get merge-sort. But even the last pass has a linear dependence chain. Not long ago, somebody posted a clever algorithm based on 4-way swaps, which is a clever way of addressing the issue.
Edit: I can't seem to locate that 4-way swapping algorithm, I swear it was posted to HN in the last year... somebody halp!
