Hacker News Reader

Comment by klyrs | Hacker News Reader

> 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

View on HN

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.

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...

Production implementation: https://github.com/facebook/folly/blob/master/folly/io/async...

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.

The paper says it's essentially bucket sort. Which was also my thirst thought when I heard about sleep sort.

This is taking it too seriously. It is just something different. To quote the article

> Bonkers, brilliant and definitely NSFW.

With 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.

If 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!

Let'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#...

You're ignoring communication overhead.

Reply on news.ycombinator.com