[mihai_ionic]

And it even has the best time bound you can get for a comparison based sort. Most OS schedulers would use a heap/priority queue internally for timers, which makes sleep sort O(n log n).

[gizmo686]

wouldn't sleep sort be O(k), where k is the largest element to be sorted? (Assuming the clock and scheduler are precise enough to achieve the correct answer the first attempt).

[mihai_ionic]

I would't really count time passing as an operation, since other programs are able to run during that time.

[gweinberg]

You could keep it linear by first going through the list to find the max, then scaling down.