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

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

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

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

I noticed this myself and decided to write a glorious example in Objective C:

http://codegolf.stackexchange.com/a/16390/11612

I wrote a version in Go http://codegolf.stackexchange.com/a/16468/11452

I just found my new favorite sorting algorithm.