Merge Sort

gistfile1.js

function merge_sort(a_array) {
  if (a_array.length < 2) {
    return a_array;
  }
  var mid = parseInt(a_array.length / 2);
  var left = a_array.slice(0, mid);
  var right = a_array.slice(mid, a_array.length);

  return merge(merge_sort(left), merge_sort(right));
}

function merge(left, right) {
  var merged = new Array ();

  while (left.length && right.length) {
    if (left[0] <= right[0]) {
      merged.push(left.shift());
    } else {
      merged.push(right.shift());
    }
  }

  while (left.length) {
    merged.push(left.shift());
  }
  while (right.length) {
    merged.push(right.shift());
  }

  return merged;
}

console.log(merge_sort([3, 5, 7, 2, 9, 1]));