merge sort

gistfile1.js

var mergeSort = function(array) {
  function merge(left, right) {
    // merge two lists, which are assumed to be sorted.
    left || (left = []);
    right || (right = []);
    var result = [];

    while (left.length > 0 || right.length > 0) {
      if (left.length > 0 && right.length > 0) {
        // if both lists have values 
        // compare the first item in each. move the smaller to the result.
        if (left[0] <= right[0]) {
          result.push(left[0]);
          left.splice(0, 1);
        } else {
          result.push(right[0]);
          right.splice(0, 1);
        }
      } else if(left.length > 0) {
        // only the left list has values
        result.push(left[0]);
        left.splice(0,1);
      } else if(right.length > 0) {
        result.push(right[0]);
        right.splice(0,1);
      }
    }

    return result;
  }

  array = array.map(function(e){ 
    return [e]; 
  });

  while(array.length > 1) {
    for(var i = 0; i < array.length; i++) {
      console.log('merging', array[i], array[i + 1]);
      array[i] = merge(array[i], array[i + 1]);
      array.splice(i + 1, 1);
    }    
  }
  
  return array[0];
};