My new favorite sort algorithm

I haven’t laughed that much in a while.

I just learned about 4chan’s brilliant Sleep Sort algorithm (2011): start a thread for each integer in the array and make it sleep X seconds where X is the value of the integer. When the thread resumes, add that integer to the end of the sorted array. Time complexity is left as an exercise for the reader.

My asynchronous JS implementation:

Array.prototype.sleepsort = function(callback){
    var self = this,
        sorted = [];
    for (var i=0,len=self.length;i<len;i++){
        (function(i){
            setTimeout(function(){
                sorted.push(self[i]);
                if (sorted.length === self.length){
                    callback(sorted);
                }
            }, self[i]);
        })(i);
    }
};

[85, 91, 25, 72, 37, 27, 24, 42, 38, 18].sleepsort(function(arr){
    console.log(arr); // [18, 24, 25, 27, 37, 38, 42, 72, 85, 91]
});

The original bash version:

#!/bin/bash
function f() {
    sleep "$1"
    echo "$1"
}
while [ -n "$1" ]
do
    f "$1" &
    shift
done
wait

Original 4chan thread
Code golf on Stack Overflow
Mandatory XKCD reference

Leave a Reply