3 ms·
No one suggested sleep sort? That's the ultimate trolling-but-almost-legitimate sorting algorithm. :)
by jeremymcanally 13y ago
No one suggested sleep sort? That's the ultimate trolling-but-almost-legitimate sorting algorithm. :)
- mihai_ionic 13y agoAnd 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.
- Moto7451 13y agoI noticed this myself and decided to write a glorious example in Objective C: http://codegolf.stackexchange.com/a/16390/11612 http://codegolf.stackexchange.com/a/16390/11612
- justinhj 13y agoI wrote a version in Go http://codegolf.stackexchange.com/a/16468/11452 http://codegolf.stackexchange.com/a/16468/11452
- pedramnegahdar 13y agoI just found my new favorite sorting algorithm.