Home/Sorting/Sleep sort
Search algorithmsCTRL K

Sleep sort

· one timer per value; whoever wakes first is printed first
/sorting/sleep-sort
TIMERS
12
one per value
FIRED
0/ 12
values in the output
ELAPSED
0 ms
the clock of the last timer
WALL TIME
98 ms
the largest value, in ms
TIES
0
equal values, kept in schedule order
timer scheduled · just firedoutput so farstill sleeping
n = 12 · seed 7 · 26 steps
step 0 / 25
Size12
sleep_sort.ts
1
function sleepSort(array: number[]): Promise<number[]> {
2
  const output: number[] = [];
3
  for (const value of array) {
4
    setTimeout(() => {
5
      output.push(value);
6
    }, value);
7
  }
8
  return new Promise((resolve) => setTimeout(() => resolve(output), Math.max(...array) + 1));
9
}
CURRENT STEP
line 1

12 values. Sleep sort starts one timer per value that sleeps that many milliseconds; whoever wakes first is printed first, so the output comes out sorted.

// how it works

Understanding Sleep sort

sleep sort · zero comparisons, and the scheduler does the work
01

The idea

Sleep sort starts one thread, or one timer, per value, and each one sleeps for as many milliseconds as its value before printing it. The smallest value wakes first, the largest last, and the printed sequence is sorted. Not a single comparison appears in the code.

The trick is that the comparisons did not disappear: the operating system keeps sleeping timers in a priority queue ordered by wake-up time, so it is the scheduler that sorts, in O(n log n), while the program waits for as long as the largest value. It is a joke with a lesson about where work hides.

02

The four stages

1
schedulea timer of value ms for each value
2
waitthe clock runs; nothing compares
3
firein value order, ties in schedule order
4
donewhen the largest value's timer fires
03

Complexity

best
O(n)work done by the program itself
average
O(max)wall time is the largest value in ms
worst
O(max)one value of a billion: eleven days
space
O(n)one timer or thread per value
04

Versus its siblings

WALL TIME · 1 000 VALUES · MS
sleep · values ≤ 100
100
sleep · values ≤ 10 000
10,000
sleep · values ≤ 1 000 000
1M
quick sort
1
merge sort
1
the comparison sorts finish in well under a millisecond; sleep sort waits for the largest value
05

Pseudocode

SLEEPSORT(array)
  for each value in array
    start a timer that, after value milliseconds, appends value to the output
  wait until the last timer fires; return the output
06

When to use

Never in production.
To show that timers, threads and event loops keep a priority queue under the hood.
07

Pitfalls

Negative values never fire; values close together can wake in the wrong order when the scheduler is busy.
Thousands of threads or timers cost far more than the sort they replace.
The output order depends on the clock, so the same input can sort differently twice.
08

History

Sleep sort was posted anonymously on 4chan's programming board in January 2011 as a shell one-liner that spawned a background sleep per argument. It spread as a joke, then as an interview question about where the hidden O(n log n) lives.

Back to Sorting