Hacker News Reader

No, the runtime complexity is just hidden in the scheduler of your OS

I don’t think this fully resolves the problem. If you had n computers and had each of them sleep for one of the numbers, and then append to a shared list, you could sort in O(n) without a scheduler.

My favorite part about this algorithm is that you can speed it up by a factor of k - for any k! - by simply dividing the time you sleep by by k.

Comparison-based sorts have O(1) complexity on the size of the elements being sorted. I.e., comparison between two numbers is a single instruction assuming numbers fit within a word. Even if you assume very very large numbers then comparison would be O(k), where k is number of bits needed to represent a number. So a more accurate runtime of O(nlogn) algorithms should be O(k.nlogn).

The runtime of this algorithm is O(n.2^k).

The O(N log N) best case only applies to comparison sorts. What's described here is not a comparison sort, and could easily be made O(N) with radix sort if the size of the numeric type is constant.