学习系列——排序——归并排序 - Problem

归并排序算法会把序列分成长度相同的两个子序列，当无法继续往下分时（也就是每个子序列中只有一个数据时），就对子序列进行归并。归并指的是把两个排好序的子序列合并成一个有序序列。该操作会一直重复执行，直到所有子序列都归并为一个整体为止。
【排序过程】
首先，要把序列对半分割。

先分成两段……

再继续往下分……

一直到每个区域大小为 1 为止。分割完毕。接下来对分割后的元素进行合并。

把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 的序列对半分割直到只有一个数据为止时，可以分成log2n 行，因此，总共有log2n 行。也就是说，总的运行时间为O(nlogn)。