归并排序是一种使用分治策略的排序算法，适用于待排序列整体无序、部分有序的情况。
1. 算法思想
递归地将待排序列等分为两个子序列，直到子序列有序（狭义得讲就是只有一个元素），再将两个子序列合并为一个新的有序序列。
2. 时间复杂度
最好情况 O(nlogn)：用递归树思想，每次递归划分合并总共都需处理n个元素，共递归划分了logn次最坏情况 O(nlogn)：对数据顺序不敏感
3. 空间复杂度 O(n)
需要额外的空间暂存新合并的有序序列
4. 稳定性
稳定。相邻序列合并，不改变同值元素的原始顺序
5. 代码实现（C语言）
首先看一下入口函数，这里创建了一个大小为n的数值，用于保存中间归并的有序序列：
void MergeSort(int *A, int n)
{
int *L = (int *)malloc(n * sizeof(int));
MSort(A, L, 0, n - 1);
free(L);
}
然后是归并排序递归处理子序列的过程：
void MSort(int *A, int *L, int low, int high)
{
int mid;
if (low < high)
{
mid = (low + high) / 2;
MSort(A, L, low, mid);
MSort(A, L, mid + 1, high);
Merge(A, L, low, high);
}
}
最后是合并两个子序列的函数：
void Merge(int *A, int *L, int low, int high)
{
int i, j, k;
int mid = (low + high) / 2;
if (low >= high)
{
return;
}
i = low;
j = mid + 1;
k = 0;
while (i <= mid && j <= high)
{
if (A[i] <= A[j])
{
L[k++] = A[i++];
}
else
{
L[k++] = A[j++];
}
}
while (i <= mid)
{
L[k++] = A[i++];
}
while (j <= high)
{
L[k++] = A[j++];
}
for (i = low; i <= high; ++i)
{
A[i] = L[i - low];
}
}
注：将子序列划分到只有一个元素为止不是好的做法，可以在子序列元素个数小于10时，使用直接选择排序处理子序列，这样能提升排序效率。
