4 ms·
this reminds me of the 4chan's sleepsort: for each number $n in the array, spin a thread that sleeps $n and then append $n to the result array.
by _ZeD_ 8y ago
this reminds me of the 4chan's sleepsort:
for each number $n in the array, spin a thread that sleeps $n and then append $n to the result array.
- tyingq 8y agoAdapted for JS: https://jsfiddle.net/dheu9q7f/ https://jsfiddle.net/dheu9q7f/
- ChristianBundy 8y agoEven worse: https://jsfiddle.net/8ta2pfny/ https://jsfiddle.net/8ta2pfny/
- diabeetusman 8y agoWould the algorithmic runtime of this be O(N)?
- bananasbandanas 8y agoNo, the runtime complexity is just hidden in the scheduler of your OS
- johnfn 8y agoI don’t think this fully resolves the problem. If you had n computers and had each of them sleep for one of the numbers, and then append to a shared list, you could sort in O(n) without a scheduler. My favorite part about this algorithm is that you can speed it up by a factor of k - for any k! - by simply dividing the time you sleep by by k.
- deleted 8y ago[deleted]
- cal97g 8y agoTechnically yes... rather genius if you only care about cpu time and not real return time.
- saurabh20n 8y agoComparison-based sorts have O(1) complexity on the size of the elements being sorted. I.e., comparison between two numbers is a single instruction assuming numbers fit within a word. Even if you assume very very large numbers then comparison would be O(k), where k is number of bits needed to represent a number. So a more accurate runtime of O(nlogn) algorithms should be O(k.nlogn). The runtime of this algorithm is O(n.2^k).
- deleted 8y ago[deleted]
- mortehu 8y agoThe O(N log N) best case only applies to comparison sorts. What's described here is not a comparison sort, and could easily be made O(N) with radix sort if the size of the numeric type is constant.
- deleted 8y ago[deleted]