Merge Sort

[barretlee]

#6 和 #8 是都是从头到尾去遍历数据，不可避免的带来很多交换操作。归并排序是一种用空间换时间的排序算法，一个数组截断成两个子数组，子数据排好序后合并到一起。

/chapters/chapter-2-sorting/2.2-mergesort/merge.js

function merge(input1, input2) {
  var i = 0, j = 0;
  var output = [];
  while(i < input1.length || j < input2.length) {
    if(i == input1.length) {
      output.push(input2[j++]);
      continue;
    }
    if(j == input2.length) {
      output.push(input1[i++]);
      continue;
    }
    if(input1[i] < input2[j]) {
      output.push(input1[i++]);
    } else {
      output.push(input2[j++]);
    }
  }
  return output;
}

上面是一个简单的合并算法，将两个有序数据合并为一个。有人应该会想到，既然一个数组可以打散成两个进行排序，那被打算的子数组是不是也可以继续被打散呢？

答案是肯定的。这是一种典型的分治思想，递归归并。

/chapters/chapter-2-sorting/2.2-mergesort/mergeRecursiveTop2Bottom.js

function mergeRecursiveTop2Bottom(input) {

  return sort(input, 0, input.length - 1);

  function sort(arr, start, end) {
    if(start >= end) {
      return;
    }
    var mid = ((end - start) >> 1) + start;
    sort(arr, start, mid);
    sort(arr, mid + 1, end);
    return merge(arr, start, mid, end);
  }

  function merge(arr, start, mid, end) {
    var i = start, j = mid + 1, tmp = [];
    for(var k = start; k <= end; k++) {
      tmp[k] = arr[k];
    }
    for(k = start; k <= end; k++) {
      if(i > mid) {
        arr[k] = tmp[j++];
        continue;
      }
      if(j > end) {
        arr[k] = tmp[i++];
        continue;
      }
      if(tmp[i] < tmp[j]) {
        arr[k] = tmp[i++];
      } else {
        arr[k] = tmp[j++];
      }
    }
    return arr;
  }
}

上面的算法是自顶向下的递归归并，简单来说就是解决很多小问题，那么大问题也就自然而然的解决了；还有一种自底向上的归并，这种归并简单来说，就是把一个大问题分解为多个小问题，多个小问题的答案就能得出大问题的答案。从解决问题的方式来看，两种处理方式是互逆的。

/chapters/chapter-2-sorting/2.2-mergesort/mergeRecursiveTop2Bottom.js

function sort(arr) {
  for(var sz = 1, len = arr.length; sz < len; sz = sz * 2) {
    for(var start = 0; start < len - sz; start += sz * 2) {
      arr = merge(arr, start, start + sz - 1, Math.min(start + sz * 2 - 1, len - 1));
    }
  }
  return arr;
}
// merge 函数同上

不过自底向上的归并，在代码上稍微难理解一些，脑海重要有清晰的画卷，知道程序跑到哪一步了，尤其还需要处理边界问题。