3 ms·

Or do a bucket sort on 32bit integers for worst case O(n) time, not O(n^2) Only half kidding… Using just 16GB RAM for a task is practically resource-constrain

• srean 3mo ago
  In my interview, several decades ago, a binary search over the bitwise representation of integers is the solution that I came up with. To the interviewers credit, who was caught by surprise by a solution he had not anticipated, he played along very sportily. He was very intrigued and happy that we came up with a solution he hadn't encountered. Later I felt stupid after reading about quick select.
• kccqzy 3mo ago
  Just do four bucket sorts, once on each byte of the 32-bit integer. (Bucket sorts are stable sorts.) I benchmarked this and it was faster than quick sort.