基本思想
归并排序采用的是分治算法的思想，其中最重要的操作就是归并操作。
主要思想是，将数组平分为A，B两部分，分别将A,B两部分排好序，然后再合并，对A排序的时候，也是同样的思路，将A分为两份，同样先分别排序，再合并。一直递归下去，直到不能再分解为止。
网上看到一张图很好的解释了这个过程：
归并算法过程.png
再用动画展示一下这个过程：
归并过程动画.gif
归并过程
假设数组已经被分解成了两个有序的数组，这个时候就应该将这两个有序数组合并成一个新的有序数组。这个时候需要额外的存储空间来辅助这个归并过程（所以归并排序不是原地排序）。
下面来张图展示这个过程：
归并过程.png
代码实现--递归版
#include <iostream>
using namespace std;
template<typename T>
void mergeSort(T arr[], int n){
// 一次性申请aux空间,
// 并将这个辅助空间以参数形式传递给完成归并排序的各个子函数
T *aux = new T[n];
__mergeSort( arr , aux, 0 , n-1 );
delete[] aux; // 使用C++, new出来的空间不要忘记释放掉:)
}
// 使用优化的归并排序算法, 对arr[l...r]的范围进行排序
// 其中aux为完成merge过程所需要的辅助空间
template<typename T>
void __mergeSort(T arr[], T aux[], int l, int r){
// 递归的终点 数组只剩一个元素的时候就可以停止了
if( l >= r ){
return;
}
int mid = l + (r-l)/2;
__mergeSort(arr, aux, l, mid);
__mergeSort(arr, aux, mid+1, r);
__merge(arr, aux, l, mid, r);
}
// 将arr[l...mid]和arr[mid+1...r]两部分进行归并
// 其中aux为完成merge过程所需要的辅助空间
template<typename T>
void __merge(T arr[], T aux[], int l, int mid, int r){
// 将原数组的数据复制给aux
for( int i = l ; i <= r; i ++ )
aux[i] = arr[i];
// 初始化，i指向左半部分的起始索引位置l；j指向右半部分起始索引位置mid+1
int i = l, j = mid+1;
for( int k = l ; k <= r; k ++ ){
if( i > mid ){ // 如果左半部分元素已经全部处理完毕
arr[k] = aux[j]; j ++;
}
else if( j > r ){ // 如果右半部分元素已经全部处理完毕
arr[k] = aux[i]; i ++;
}
else if( aux[i] < aux[j] ) { // 左半部分所指元素 < 右半部分所指元素
arr[k] = aux[i]; i ++;
}
else{ // 左半部分所指元素 >= 右半部分所指元素
arr[k] = aux[j]; j ++;
}
}
}
结论
归并排序总的平均时间复杂度为O(nlogn)，最好，最坏，平均时间复杂度均为O(nlogn)。所以归并排序是稳定的排序算法，缺点是需要额外的存储空间（貌似也有原地归并排序，无需额外存储空间，待研究）。
