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