title: Is there a way to sort arrays without allocating any memory?
body: <p>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.</p>
  
  <p>I've tried various approaches:</p>
  
  <ul>
  <li>List.Sort() with IComparer, computing the key every time: super slow</li>
  <li>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...</li>
  <li>Array.Sort(keyArray, valueArray): horrendous! slow &amp; generates 256KB of GC/frame!</li>
  </ul>
  
  <p>It's a shame because SortedList seemed perfect for the job, is there any GC-free alternative that I'm missing?</p>