title: Sorting 10 million objects in O(n) time and O(1) extra memory
body: <p>I'm trying to find an answer to an interview question I got recently but wasn't able to solve. I was asked to sort 10 million objects (each contains a 10-bit integer and a unique string value) by the 10-bit integer in place using O(1) space and O(n) time. For all intensive purposes, the string value just makes the problem more difficult, but you don't sort the objects by it.</p>
  
  <p>I was thinking of using counting sort however, that would only work if I was just sorting the 10-bit integers. Sorting the objects makes things a bit more complicated, since I need to keep track of their unique string values. I looked at radix sort, but it appears to use O(n) as worst-case.</p>
  
  <p>Is there some type of sort that I'm missing?</p>