Sleepsort

Sleepsort might be a joke, but its implementation demonstrates three very important things about javascript: closures, asynchronous functions, and variable hoisting.

It is therefore an excellent example for a beginner to study to understand javascript better.

The Naive Implementation

function sleepsort (input) {  
  for(var i=0; i<input.length; ++i) {
    setTimeout(function () {
      console.log(input[i]);
    }, input[i] * 1000);
  }
};

sleepsort([3,1,2]);  

Output:

undefined  
undefined  
undefined  

What happened here? Why did we get three undefined elements?

If we modify the example a little bit, the reason is clear:

function sleepsort (input) {  
  for(var i=0; i<input.length; ++i) {
    setTimeout(function () {
      console.log(input[i]);
    }, input[i] * 1000);

    console.log('i is ' + i);
  }
};

sleepsort([3,1,2]);  

Output:

i is 0  
i is 1  
i is 2  
undefined  
undefined  
undefined  

The for loop kept running, incrementing the value of i. By the time the callback functions ran, the value of i was 3, which was out of bounds of the input array.

This demonstrates closure, which is the ability of a function to “remember” the scope it was created in, and access the variables in that scope.

The Naive Fix

A beginner would likely try to fix the problem with this code:

function sleepsort (input) {  
  for(var i=0; i<input.length; ++i) {
    var j = i; // copy i into j.

    setTimeout(function () {
      console.log(input[j]);
    }, input[j] * 1000);
  }
};

sleepsort([3,1,2]);  

Output:

2  
2  
2  

Why did we get three 2s this time? The reason is because of hoisting. All variable declarations in javascript are “hoisted” to the top of the scope they are in. Since only functions create new scopes in javascript, this means that our code was equivalent to this:

function sleepsort (input) {  
  var j;

  for(var i=0; i<input.length; ++i) {
    j = i; // copy i into j.

    setTimeout(function () {
      console.log(input[j]);
    }, input[j] * 1000);
  }
};

sleepsort([3,1,2]);  

Unlike languages like Java and C, the for loop did not have its own scope. Thus, j was last assigned the value of 2 before the loop ended, and that was the element that was printed three times.

The Real Fix

The real solution to this problem is to create a new scope. By wrapping our timeout code in an immediately invoked function expression (IIFE), we create a variable j in a new scope and assign it the current value of i. Since j is in a new scope, it is untouched by future iterations of the loop.

function sleepsort (input) {  
  for(var i=0; i<input.length; ++i) {
    (function (j) {
      setTimeout(function () {
        console.log(input[j]);
      }, input[j] * 1000);
    })(i);
  }
};

sleepsort([3,1,2]);  

Output:

1  
2  
3  

Optimization

While optimizing sleepsort is somewhat of a laughing matter, creating functions inside a loop is almost always a bad idea. The following code is equivalent and resolves this problem:

function sleepsort (input) {

  function sort (j) {
    setTimeout(function () {
      console.log(input[j]);
    }, input[j] * 1000);
  };

  for(var i=0; i<input.length; ++i) {
    sort(i);
  }
};

sleepsort([3,1,2]);  

I hope that helped your understanding of closure, asynchrony, and hoisting!

Is this really O(n)?

No, it’s actually using your operating system’s insertion sort.

This code is all available on github and of course, npm.