归并排序

<b>归并排序</b>是建立在归并操作上的一种有效的排序算法。该算法是采用分治法（Divide and Conquer）的一个非常典型的应用。

归并操作(merge)，也叫归并算法，指的是将两个已经排序的序列合并成一个序列的操作。归并排序算法依赖归并操作。

归并操作步骤如下：（两个有序序列分别用A[aMax]、B[bMax]表示）

1）设定两个指针（iA、iB），最初位置分别为两个已经排序序列的起始位置；

2）比较A[iA]、B[iB]，选择较小的放入合并空间，并移动对应指针到下一位置；

3）重复步骤二直至读完序列A或B其中之一的数据；

4）将另一序列剩下的所有元素直接复制到合并序列尾。

归并操作实现代码如下：

从归并操作到归并排序：

通过归并操作我们可以将两个有序的序列合并成一个有序的序列，那我们怎么实现一个无序数组的排序呢？我们会想“如果将这个无序的数组分解成两个有序的数组就好了。”但如何让这二组组内数据有序呢？“可以将这两个数组各自再分成两组”。对，依次类推，就这样分下去，最终我们得到的是两个一个元素的数组（我们可以认为它是有序的了），反过来我们通过一次次归并操作，便可得到一个有序的数组。对，这是递归的应用。

前面，不知不觉还是说的有点绕，整理一下，其基本思路如下：

1）我们将一个要排序的无序数组，分解成两个数组；

2）重复步骤一，直到子数组只有一个元素；

3）使用归并操作获取所求。

实现代码如下：

华丽的分割线后，附上测试代码：

在Release环境下：

排序10000条数据，约2.3ms.

排序20000条数据，约5ms：

排序200000条数据，约45ms。

另，附冒泡算法排序200000条数据的测试结果以做对比：