(go语言设计与实现)(go语言设计与实现 电子书)

排序算法中有一个是非常重要的算法思想，叫做合并算法(或归并算法，Merge Sort)，这是一种分治思想，即将数组不断一分为二，然后再逐个合并排序。掌握这个思想以后就可以将复杂的问题不断简化，然后逐个击破。以下用Go语言来演示下具体实现。

实现步骤

1、先写一个合并已排序数组的函数，使两个数组合并后排序。

原理是不断遍历两个数组，比较其中最小的项，将小的项添加到新数组中，然后移动小项所在的数组指针，用下一个小的项再进行比较，直到数组被遍历完成为止。

2、再写一个合并排序的函数。这个函数是入口函数，主要是通过递归来不断拆分和调用合并函数。

其主要作用是：1）将数组不断一分为二，从外向里递归调用，直到子数组只剩下1个元素；2) 不断合并左右子数组，从内向外，直到递归执行完成，最终得到排序后的新数组。

3、验证程序。分别构造两组数据来验证，可以看到最后结果符合预期，新数组已经排好序。