排序

[jeezliu]

// 归并排序
function merge(left, right) {
  var result = [];

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

  return result.concat(left).concat(right);
}
function mergeSort(arr) {
  if(arr.length === 1) {
    return arr;
  }

  var mid = Math.floor(arr.length / 2),
      left = arr.slice(0, mid),
      right = arr.slice(mid);
  
  return merge(mergeSort(left), mergeSort(right));
}
// 迭代版
function mergeSort(arr) {
  if(arr.length === 1) {
    return arr;
  }

  var work = arr.map(function(x) {
    return [x];
  })

  for(var lim = arr.length; lim > 1; lim = Math.floor((lim + 1) / 2)) {
    for(var j = 0, k = 0; k < lim; k = k + 2, j++) {
      work[j] = merge(work[k], work[k+1]);
    }
  }

  return work[0];
}