归并排序

归并排序（mergesort）采用分治的思想，将输入数据对列分为若干段，递归地将这些段排好，然后再通过师并的操作把这几段拼起来，从而将整个对列排序。

 

典型的归并是2路归并排序，过程如下所示：

 

例如数组A有以下7个数据：

49 38 65 97 76 13 27

[49] [38] [65] [97] [76] [13] [27]//看成由长度为1的7个子序列组成

[38 49] [65 97] [13 76] [27] //看成由长度为1或2的4个子序列组成

[38 49 65 97] [13 27 76] //看成由长度为4或3的2个子序列组成

[13 27 38 49 65 76 97]

归并算法的时间复杂度是o(nlogn)，但空间复杂度却是o(n)，为了解决归并算法空间复杂度的问题，很多研究者都做了相关的研究，最早在1969年的时候，M. A. Kronrod就解决了这个问题，使其空间复杂度为o(1)，也就是说不占用了额外存储空间。

《数据结构》P213对此空间复杂度为0(1)的归并算法进行了较详细的介绍，过程比较复杂，需慢慢研究体会。

此文待继！！！