Is there a way to sort arrays without allocating memory?

Question

I need to sort a rather large collection very often (high hundreds / low thousands of elements), that is, each frame at a speed of 60 frames per second (I use Unity). Computing a key for each item is slow, so it needs to be cached.

I tried various approaches:

• List.Sort () with IComparer, each time computing the key: super slow
• SortedList: MUCH faster, but generates GC allocs (30KB / frame): why? Are they short (I use long)? is the highlighted key / value pair? If I complete the long class, GC will be reduced by half, so I assume that these are “both”: 1 alloc for the pair, one alloc for entering the key, if it is a value type ...
• Array.Sort (keyArray, valueArray): awful! Slow and generates 256 KB GC / frame!

This is a shame because the SortedList seemed perfect for the job, is there any GC-free alternative that I am missing?

Answer 1

If the compute keys are so slow, you can add a property keyto your product class, calculate it before sorting, and then use your first method by IComparersimply comparing the keys.