归并排序 - acgtyrant/Algorithm-and-Data-Structure GitHub Wiki

其实很早就写好了，但一直有奇怪的 bug, 最近才扒出并捏死。

其实其实我感觉归并排序的代码复杂度要比快速排序复杂多了。

其一，首先得实现两种子函数，一是 Sort, 二是 Merge, 至于实现就不哆嗦了。

其二，我实现的归并排序并不是 in-place 算法，而且由于模板的限制，我不得不引入一个额外的第三参数 temporary_iterator, 用来代表临时空间 temporary_vector 的迭代器：

template <typename RandomIterator>
void MergeSort(
    RandomIterator first,
    RandomIterator last,
    RandomIterator temporary_first) {
...
};  

其三，为了避免递归 Sort 中不停地把 temporary_vector 中的值赋值到本体上，我们可以干脆在递归之递归中交换参数的位置，实现轮流倒排。说实话这蛮考验脑力的，我想了半天，最后还是被一开始的

mergesort::Sort(first, last, temporary_first); 
std::copy(temporary_first, temporary_first + (last - first), first);

所启发：既然我写了这两个语句，就说明我在假定这个算法对 [first, last) 的排序结果会被储存到 temprary_first 所指向的容器上。所以就在它里面的两个 Sort 递归函数中把迭代器参数位置颠倒过来，至于 Merge 则不用，毕竟 Merge 的实现说得很清楚了，既然 mergesort::Sort(first, last, temporary_first) 要把排序结果储存到 temporary_first 上，那么 Merge 的迭代器参数位置毋庸置疑地与它一致。此外，我还从中学到，迭代器运算可以很好地代替传统的索引值，比如 last - first 就等于其 size, 且 temporary + (last - first) 一样也做到了出色的同・步长索引。

其四，当迭代器范围很小时，可以直接上 InsertionSort, 不过别忘了这时我们无法确定所用的迭代器范围 [first, last) 是来自正体还是 temporary_vector. 其实没必要判断，直接把它们 std::copy 复制到 temporary_first 所指的容器即可，这么一来在递归函数的终点里，正体与 temporary_vector 的值就完全一致，自然免去鸡生蛋蛋生鸡之恼：

if (last - first < mergesort::cutoff) {
  InsertionSort(first, last);
  std::copy(first, last, temporary_iterator);
  return;
}