Sleep Sort: Mechanism, Complexity Analysis & Interactive Visualizer

Sleep Sort

A unique concurrency-based sorting algorithm: spawns a separate thread for each element, sleeping for a duration proportional to the element value before writing it to the output.

How it works

Sleep Sort was published anonymously on the 4chan imageboard in 2011. It quickly went viral in developer communities because of its hilarious design that abuses thread sleeping mechanisms to sort without performing a single element-to-element comparison:

1. **Thread Spawning:** For each element \(x\) in the input array, spawn a concurrent background thread (or set an asynchronous timeout/timer).
2. **Proportional Sleeping:** In each thread, put the execution to sleep for a duration proportional to the value of \(x\) (e.g. \(sleep(x)\) or \(sleep(x \cdot 10)\) milliseconds).
3. **Wakeup Write:** When a thread wakes up, it immediately appends the value of \(x\) to a global output list.
4. **Sorted Output:** Because smaller values wake up sooner than larger values, the elements write themselves to the output list in fully sorted order!

Complexity

Interactive visualization

Pseudocode

procedure sleepSort(A):
  outputList ← empty list
  
  parallel for each val in A:
    sleep(val)
    outputList.append(val)

JavaScript implementation

// Asynchronous JavaScript Sleep Sort
async function sleepSort(arr) {
  const sorted = [];
  
  const sleepPromise = (val) => {
    return new Promise(resolve => {
      setTimeout(() => {
        sorted.push(val);
        resolve();
      }, val * 10); // sleep proportional to val
    });
  };
  
  await Promise.all(arr.map(val => sleepPromise(val)));
  
  for (let i = 0; i < arr.length; i++) arr[i] = sorted[i];
  return arr;
}

Pros and cons

When (not) to use it

• Humorous presentations: Hilarious to demo, showing how concurrency can be abused to perform logical tasks.
• Real systems: Never! CPU execution jitter will cause elements to write out-of-order, failing correctness.