Is there a way to sort arrays without allocating any memory?

Question

I need to sort a rather big collection (high hundreds/low thousands of items) very frequently, that is every frame at 60 fps (I'm using Unity). Computing the key for each item is sort of slow so it needs to be cached.

I've tried various approaches:

• List.Sort() with IComparer, computing the key every time: super slow
• SortedList: MUCH faster, but generates GC allocs (30KB/frame): why? is they key boxed (I'm using a long)? is the key/value pair allocated? If I wrap the long in a class, the GC is halved, so my guess is "both": 1 alloc for the pair, one alloc to box the key if it's a value type...
• Array.Sort(keyArray, valueArray): horrendous! slow & generates 256KB of GC/frame!

It's a shame because SortedList seemed perfect for the job, is there any GC-free alternative that I'm missing?

Answer 1

If computing keys is so slow, you can add key property to your item class, calculate it before sorting, and then use your first method with IComparer simply comparing keys.