《我的第一本算法书》阅读笔记 2-6 归并排序
归并排序算法会把序列分成长度相同的两个子序列，当无法继续往下分时（也就是每个子序列中只有一个数据时），就对子序列进行归并。归并指的是把两个排好序的子序列合并成一个有序序列。该操作会一直重复执行，直到所有子序列都归并为一个整体为止。
首先，要把序列对半分割。
先分成两段……
再继续往下分……
分割完毕。接下来对分割后的元素进行合并。
把6和4合并，合并后的顺序为[4, 6]。
接下来把3和7合并，合并后的顺序为[3, 7]。
下面，我们来看看怎么合并 [4, 6]和[3, 7]。合并这种含有多个数字的子序列时，要先比较首位数字，再移动较小的数字。
由于4＞3，所以移动3。
同样地，再次比较序列中剩下的首位数字。
由于4＜7，所以移动4。
由于6＜7，所以移动6。
最后移动剩下的7。
递归执行上面的操作，直到所有的数字都合为一个整体为止。
这里也要比较两个子序列中的首位数字。
由于3＞1，所以移动1。继续操作……
合并完成，序列的排序也就完成了。
解说
归并排序中，分割序列所花费的时间不算在运行时间内（可以当作序列本来就是分 割好的）。在合并两个已排好序的子序列时，只需重复比较首位数据的大小，然后移动较 小的数据，因此只需花费和两个子序列的长度相应的运行时间。也就是说，完成一行归并所需的运行时间取决于这一行的数据量。
看一下上面的图便能得知，无论哪一行都是 n 个数据，所以每行的运行时间都为 O(n)。 而将长度为 n 的序列对半分割直到只有一个数据为止时，可以分成 行，因此，总共有 行。也就是说，总的运行时间为 O(nlogn)，这与前面讲到的堆排序相同。
归并排序每次递归需要用到一个辅助表，长度与待排序的表相等，虽然递归次数是O(log2n)，但每次递归都会释放掉所占的辅助空间，所以下次递归的栈空间和辅助空间与这部分释放的空间就不相关了，因而空间复杂度是O（n）。
《我的第一本算法书》 [日]石田保辉 宫崎修一/著 张贝/译
