Sleep Sort in JavaScript | http://t.co/nWJACyK

sleep-sort.js

// from: http://dis.4chan.org/read/prog/1295544154/170
function sleepSort(list, callback) {
  const result = [];

  list.forEach((i) => setTimeout(() => {
    result.push(i);

    if (result.length == list.length) {
      callback(result);
    }
  }, i));

}

const list = [4, 5, 7, 1, 2, 4, 5];

sleepSort(list, alert);

Sleep Sort – The King of Laziness / Sorting while Sleeping

Sleep sort was presented anonymously on 4chan(unavailable) and has been discussed on Hacker News.

In this algorithm we create different threads for each of the elements in the input array and then each thread sleeps for an amount of time which is proportional to the value of corresponding array element.

Hence, the thread having the least amount of sleeping time wakes up first and the number gets printed and then the second least element and so on. The largest element wakes up after a long time and then the element gets printed at the last. Thus the output is a sorted one.

All this multithreading process happens in background and at the core of the OS. We do not get to know anything about what’s happening in the background, hence this is a “mysterious” sorting algorithm.

Limitations

• This algorithm won’t work for negative numbers as a thread cannot sleep for a negative amount of time.
• Since this algorithm depends on the input elements, so a huge number in the input array causes this algorithm to slow down drastically (as the thread associated with that number has to sleep for a long time). So even if the input array element contains only 2 elements, like- {1, 100000000}, then also we have to wait for a much longer duration to sort.
• This algorithm doesn’t produce a correct sorted output every time if using threads. This generally happens when there is a very small number to the left of a very large number in the input array.
  For example – {34, 23, 1, 12253, 9}.
  The output after sleep sorting is {9, 1, 23, 34, 1223}

Time Complexity

Although there are many conflicting opinions about the time complexity of sleep sort, but we can approximate the time complexity using the below reasoning-

Since Sleep() function and creating multiple threads is done internally by the OS using a priority queue (used for scheduling purposes). Hence inserting all the array elements in the priority queue takes O(Nlog N) time. Also the output is obtained only when all the threads are processed, i.e- when all the elements ‘wakes’ up. Since it takes O(arr[i]) time to wake the ith array element’s thread. So it will take a maximum of O(max(input)) for the largest element of the array to wake up. Thus the overall time complexity can be assumed as O(NlogN + max(input)),
where, N = number of elements in the input array, and input = input array elements

Auxiliary Space

All the things are done by the internal priority queue of the OS. Hence auxiliary space can be ignored.

Conclusion

Sleep Sort is related to Operating System more than any other sorting algorithm. This sorting algorithm is a perfect demonstration of multi-threading and scheduling done by OS.

The phrase “Sorting while Sleeping” itself sounds very unique. Overall it is a fun, lazy, weird algorithm. But as rightly said by someone- “If it works then it is not lazy”.

A lot of this text is taken from this article by Rachit Belwariar
photo of original 4chan post it taken from this lecture