5 ms·
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 mak
by mihai_ionic 13y ago
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 13y agowouldn'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 13y agoI would't really count time passing as an operation, since other programs are able to run during that time.
- gweinberg 13y agoYou could keep it linear by first going through the list to find the max, then scaling down.