This is one of the most unique and fun sorting algorithms on planet earth, in which the time required to complete sorting depends on the size of each individual element rather than the number of elements. But is there any practical use case for it where it is actually efficient? I mean when dealing with large numbers, it's gonna be a gruesome idea to use sleep sort. But what about very, very, very small numbers? Does it outperform Merge Sort there?

CodePudding user response：

While it is an interesting approach to sorting, it has no practical use as it won't beat out other algorithms like merge sort in any meaningful way. Even at very small numbers, it doesn't give any practical advantage in terms of memory or computation time.

CodePudding user response：

But is there any practical use case for it where it is actually efficient?

No.

But what about very, very, very small numbers?

No. You are going to have to create an impractically large number threads, each of which has to sleep. In a typical modern programming language creating each thread is expensive and uses a lot of memory for the thread stack.

In theory "sleep sort" is O(N) ... if you ignore some seriously bad scaling problems which probably make it worse than O(N).

But for the same problem (lots of very small numbers), a counting or bucket sort will also be O(N) and it will have a much smaller constant of proportionality. Also, the memory utilization for the counters is bounded by the range of the numbers you are sorting ... and log(N).

Now that I think about it, if you have N threads sleeping for different numbers of seconds, the operating system has maintain a list of threads that is sorted by their respective wakeup times. That's probably going to O(NlogN) or worse. Basically "sleep sort" is a con.