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?
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 scam :-).