4 ms·
> Sleep sort is an O(N) sorting algorithm for non-negative integers. No, it is not. It's O(N+M) where M is the largest value in the list. And, notably, it ca
by klyrs 5y ago
> Sleep sort is an O(N) sorting algorithm for non-negative integers.
No, it is not. It's O(N+M) where M is the largest value in the list. And, notably, it can fail if the time to schedule the jobs takes longer than the smallest difference between elements in the list
- raymondh 5y agoAlso, sleep() just delegates the sorting responsibility to a scheduler which likely uses on O(log n) heap algorithm to identify the next scheduled event.
- rileymat2 5y agoThis is taking it too seriously. It is just something different. To quote the article > Bonkers, brilliant and definitely NSFW.
- EquallyJust 5y agoHashed hierarchical timing wheels is a cool very specialized data structure to make this efficient. The paper claims it's O(1) to start, stop and maintain timers which is much more efficient than O(log n). Given there's n timers and O(1) operations I'm not sure where the O(n log n) fits in here. Possible in the minimum number of ticks? http://www.cs.columbia.edu/~nahum/w6998/papers/sosp87-timing-wheels.pdf http://www.cs.columbia.edu/~nahum/w6998/papers/sosp87-timing... Production implementation: https://github.com/facebook/folly/blob/master/folly/io/async/HHWheelTimer.h https://github.com/facebook/folly/blob/master/folly/io/async...
- klyrs 5y agoProbably this bit from section 5 > If we can guarantee that all timers are set for periods less than MaxInterval, this modified algorithm takes O(1) latency for START_TIMER, STOP_TIMER, and PER_TICK_BOOKKEEPING. I think that puts this in the same class as counting sort.
- sly010 5y agoThe paper says it's essentially bucket sort. Which was also my thirst thought when I heard about sleep sort.
- deleted 5y ago[deleted]
- BearsAreCool 5y agoWith a linear time O(N) first pass you can identify the minimum element in the list. This reduces M from being the largest element to being the difference between the largest and the smallest element.
- rileymat2 5y agoIf we are playing with this, why not take one pass to find the largest element, then another pass to divide each element in the list by that number, leaving it 3N+M/M. Edit: Why divide by m, when you can divide by M*C. Where C will speed this portion up by a factor!
- david_allison 5y agoLet's do better. You can find the largest element in a list in O(1) time with n^2 processors[0]*. Division of the list by that number is O(1) with n processors Therefore the operation is O(1) [0]* on a CRCW PRAM https://www.cpp.edu/~gsyoung/CS535/CS535Notes/Part2PRAM.pdf#page=1 https://www.cpp.edu/~gsyoung/CS535/CS535Notes/Part2PRAM.pdf#...
- lupire 5y agoYou're ignoring communication overhead.