Are there tricks for getting proper sort ordering on particle systems?
First option should be to make all particles able to go through the same pipeline. Perhaps with an uber shader. That way you can batch them all.

Positive ieee floating point numbers can be sorted like unsigned integer. And there are O(n) algorithms to sort those for example radix sort.