4 ms·

Also, 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 ago
  This is taking it too seriously. It is just something different. To quote the article > Bonkers, brilliant and definitely NSFW.
• EquallyJust 5y ago
  Hashed 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 ago
    Probably 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 ago
    The paper says it's essentially bucket sort. Which was also my thirst thought when I heard about sleep sort.
• deleted 5y ago
  [deleted]