Post

Linear Sort xkcd.com/3026

Sleepsort also sorts in linear time, and is faster: www.cs.princeton.edu/courses/arch...

Sleep sort is going to require the kernel to maintain a sorted list of sleep expiration times, which will be worse than linear. 😅

That sounds like an environment problem The algorithm theoretically still satisfies linear time

*dull mode on* No, it doesn't. As stated in comments above the time complexity of the sleepsort depends not on the quantity of the elements in input data, but on elements' values. Taking the O for the sleep(n) itself as O(n) we get the n=MAXn(Vi) for the best case (enough CPUs) and ...

PS. It's better keep in mind the "time" in "big-O time complexity" isn't about a time in seconds or any time units, but about the operations/steps quantity. And not the absolute quantity but a function, which would asymptotically close to the quantity. It's about scalability, not the absolute time

In addition, I would not consider sleepsort as a sorting algorithm at all, since it's defined only for natural numbers. If you get an abstract data element with only comparator defined, you will have to associate an ordinal number to each element first, what implies ... sorting them.

For sure. But imagine we had a hashing function without many collisions to map each element to a time slice. Of course one could directly sort using said function, but wouldn't it be interesting to dispatch multiple threads and have each schedule an insertion? We could cook this a little more!