基本思想
归并排序（MERGE-SORT）是利用归并的思想实现的排序方法，该算法采用经典的分治（divide-and-conquer）策略（分治法将问题分(divide)成一些小的问题然后递归求解，而治(conquer)的阶段则将分的阶段得到的各答案"修补"在一起，即分而治之)。
分而治之
可以看到这种结构很像一棵完全二叉树，本文的归并排序我们采用递归去实现（也可采用迭代的方式去实现）。分阶段可以理解为就是递归拆分子序列的过程，递归深度为log2n。
合并相邻有序子序列
再来看看治阶段，我们需要将两个已经有序的子序列合并成一个有序序列，比如上图中的最后一次合并，要将[4,5,7,8]和[1,2,3,6]两个已经有序的子序列，合并为最终序列[1,2,3,4,5,6,7,8]，来看下实现步骤。
"治" 代码实现
图看完了，现在来看代码吧。
void merge(int *arr, int left, int mid, int right ,int *temp)
{
int i = left;//左序列指针
int j = mid+1;//右序列指针
int t = 0;//临时数组指针
while (( i <= mid) && ( j <= right))
{
if (arr[i] < arr[j])
{
temp[t++] = arr[i++];
}
else
{
temp[t++] = arr[j++];
}
}
while (i <= mid)//将左边剩余元素填充进temp中
{
temp[t++] = arr[i++];
}
while (j <= right)//将右序列剩余元素填充进temp中
{
temp[t++] = arr[j++];
}
t = 0;
//将temp中的元素全部拷贝到原数组中
while (left <= right)
{
arr[left++] = temp[t++];
}
}
这个函数有点难理解，我们还是拿上图的具体例子来说吧。执行merge(arr, 0, 4, 8, temp)，其实就是把{4,5,7,8}(暂时称为左子数组)和{1,2,3,6}(右子数组)两个已经有序的子序列，合并为最终序列{1,2,3,4,5,6,7,8}。先比较左右子数组的第一个元素的大小，把较小的存到临时数组的第一个元素，然后把对应的子数组的指针加1，继续比较。直到左右子数组中某一个子数组完全被复制到了temp中，接下来的while循环做的事情就是把剩下的子数组中的剩余元素都复制进temp。由于不知道是左子数组还是右子数组剩余元素，所以都要写一遍。最后把temp数组的元素拷贝到arr中，arr就排序好了。
"分" 代码实现
void MSort(int *arr, int left, int right, int *temp)
{
// if (left = right) return;
if (left < right)
{
int mid = (left + right) / 2;
MSort(arr, left, mid, temp);//左边归并排序，使得左子序列有序
MSort(arr, mid+1, right, temp);//右边归并排序，使得右子序列有序
merge(arr, left, mid, right, temp);//将两个有序子数组合并操作
}
}
"分"采用了递归的方法，采用了折半的策略，先归并左子数组，再归并右子数组，再把左右子数组合并。有的读者可能觉得MSort函数没有终止条件，其实它是有的，隐含的条件是这个if (left = right) return;，因为当left = right时，其实只有一个元素，肯定是有序的。
归并排序递归版 代码实现
// 归并排序递归版
void MergeSort(int *arr, int length)
{
int *temp = (int *)malloc(sizeof(int) * length);//在排序前，先建好一个长度等于原数组长度的临时数组，避免递归中频繁开辟空间
MSort(arr, 0, length-1, temp);
free(temp);
}
归并排序是稳定排序，它也是一种十分高效的排序，能利用完全二叉树特性的排序一般性能都不会太差。从上文的图中可看出，每次合并操作的平均时间复杂度为O(n)，而完全二叉树的深度为|log2n|。总的平均时间复杂度为O(nlogn)。而且，归并排序的最好，最坏，平均时间复杂度均为O(nlogn)。
