Post

Linear Sort xkcd.com/3026

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

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 ...

...n=SUMn(Vi) for the worst case - on a single core. It actually makes big-O notation useless here, since it cannot show how the algorithm scales on elements quantity. Actually, it's impossible to find any asymptotic function for such case, since the input data values unknown