Hacker News Reader

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-constrained programming these days…

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.

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.

Reply on news.ycombinator.com