[libealistand]

> Not only it not constant time, it's not even it's polynomial

You understand that this is part of the joke, right?

If we really want to get down to the details and kill the joke, then you don't actually need to wait real time. Computational complexity is concerned with steps in a computational model, not how much time passes on a clock. Sleep sort uses OS scheduler properties and in a virtual time environment, time advances to the next scheduled event. That's what brings you back to actual polynomial complexity, if you assume this kind of thing as your computational model.

> - it's psuedo-polynomial.

If you lecture people then please at least get your spelling right.

[orangesite]

This is really what makes the joke work IMO.

Haskell's runtime and the OS it executes on exist only as a transient implementation detail of what is, literally, a pure environment!

[bmacho]

I still don't get it. Sleep sort still needs O(n) Haskell-steps, while for example sorting in bash is just 2 bash-steps, calling it, and receiving the output.

I fail to see the joke, really. I only see false and nonsense statements, which still could be funny or interesting, but I don't see how?

[xena]

The "constant time" is wall clock time, where it will be at least the biggest value times the constant microseconds plus like 5% for overhead like the garbage collector.

[fenomas]

Complexity analysis deals with asymptotic cases where N gets arbitrarily large. Sleepsort would take the same wall time to sort [1,2] and [1,2,1,2] - but it would presumably take somewhat longer to sort an array of 1e10 ones and twos, because it's not a constant time algorithm.

On the joke part, sleepsort is intrinsically an extremely funny concept and I think everyone here gets that. But "constant time" has a rigorous/pedantic definition, which sleepsort doesn't meet, so I think for some readers calling it that kills the joke (in the same sort of way that it would kill the joke if TFA's code snippets used lots of invalid syntax).

[musicale]

I'd never seen sleepsort before, so I thought it was funny. ;-)

I like the idea of (ab)using the scheduler to sort numbers.

Now I'm inspired to make my own "sorting" routine, maybe touching filenames and then sorting them with `ls -n`, or rendering triangles and then ripping them off in z-plane order, or stuffing frames into a video and then playing it back.