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

*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

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