原理：
设两个有序的子序列(相当于输入序列)放在同一序列中相邻的位置上：array[low..m]，array[m + 1..high]，先将它们合并到一个局部的暂存序列 temp (相当于输出序列)中，待合并完成后将 temp 复制回 array[low..high]中，从而完成排序。
在具体的合并过程中，设置 i，j 和 p 三个指针，其初值分别指向这三个记录区的起始位置。合并时依次比较 array[i] 和 array[j] 的关键字，取关键字较小（或较大）的记录复制到 temp[p] 中，然后将被复制记录的指针 i 或 j 加 1，以及指向复制位置的指针 p加 1。重复这一过程直至两个输入的子序列有一个已全部复制完毕(不妨称其为空)，此时将另一非空的子序列中剩余记录依次复制到 array 中即可
备注：图片原理来源：upload/201811191117470152.png" alt="" style="margin: 0px; padding: 0px; border: 0px; max-width: 900px; height: auto;" />
先"分割"再"合并"
从上图可以看出，我们首先把一个未排序的序列从中间分割成2部分，再把2部分分成4部分，依次分割下去，直到分割成一个一个的数据，再把这些数据两两归并到一起，使之有序，不停的归并，最后成为一个排好序的序列。
测试用例：
#ifndef INC_02_MERGE_SORT_SORTTESTHELPER_H #define INC_02_MERGE_SORT_SORTTESTHELPER_H #include <iostream> #include <algorithm> #include <string> #include <ctime> #include <cassert>using namespace std; namespace SortTestHelper { // 生成有n个元素的随机数组,每个元素的随机范围为[rangeL, rangeR] int *generateRandomArray(int n, int range_l, int range_r) { int *arr = new int[n]; srand(time(NULL)); for (int i = 0; i < n; i++) arr[i] = rand() % (range_r - range_l + 1) + range_l; return arr; } // 生成一个近乎有序的数组 // 首先生成一个含有[0...n-1]的完全有序数组, 之后随机交换swapTimes对数据 // swapTimes定义了数组的无序程度 int *generateNearlyOrderedArray(int n, int swapTimes){ int *arr = new int[n]; for(int i = 0 ; i < n ; i ++ ) arr[i] = i; srand(time(NULL)); for( int i = 0 ; i < swapTimes ; i ++ ){ int posx = rand()%n; int posy = rand()%n; swap( arr[posx] , arr[posy] ); } return arr; } // 拷贝整型数组a中的所有元素到一个新的数组, 并返回新的数组 int *copyIntArray(int a[], int n){ int *arr = new int[n]; //* 在VS中, copy函数被认为是不安全的, 请大家手动写一遍for循环:) copy(a, a+n, arr); return arr; } // 打印arr数组的所有内容 template<typename T>
