Have you tried prefix-sum? In my game code I used the Nvidia key/offset sort for a long time, but I've since replaced that for all of my physics and spatial queries.

There are cases where even though the sort executes more instructions that the size of the elements/code still fits into some Ln cache level and makes it faster, but in general the prefix approach comes out ahead.