归并排序是建立在归并操作基础上的一种有效地排序算法。也是几大优秀排序算法中稳定的一种。其时间复杂度为O(nlogn)，但空间复杂度是O(n)这点是它的一个劣势。原
因在于需要把原始数据划分为两两有序的数据，然后再两两合并成最终的一个数组或是链表。
那么下面就来仔细探讨下归并排序算法的原理。
首先，是一个合并两个有序数组成为一个数组的算法。
void merge(int a[], int n, int b[], int m, int c[])
{
int i, j, k;
i = j = k = 0;
while (i < n&&j < m)
{
if (a[i] <= b[j])
c[k++] = a[i++];
else
c[k++] = b[j++];
}
while (i < n)
c[k++] = a[i++];
while (j < m)
c[k++] = b[j++];
}
思路就是，比较两个数组A和B当中的元素，谁小就把谁赋给C，同时下标同时前进，直到其中一个数组末尾。如果AB两个数组中的一个没有到末尾，那么将剩下的元素赋给C数组的后面元素。这样的思路也同样适用于链表的合并。
但是此时是针对一个数组，所以我们需要对merge函数进行调整。
void merge(int a[], int first, int mid, int last, int temp[])
{
int i = first;
int j = mid+1;
int k = 0;
while (i <=mid && j<=last)
{
if (a[i] <= a[j])
{
temp[k++] = a[i++];
}
else
{
temp[k++] = a[j++];
}
}
while (i <=mid)
{
temp[k++] = a[i++];
}
while (j <=last)
{
temp[k++] = a[j++];
}
for (int i = 0; i < k; i++)
{
a[first+i] = temp[i]; //非常重要，为什么是first+i？必须要有first，因为是归并
}//要分别合并，必须要有起点first
}
那么第二步，如何把一个数组分成两个数组，然后再继续划分成四个，在如此划分下去，知道划分成当个元素的数组？那么就是用到了递归调用的思想了。
A[0,N-1]划分成A[0,mid-1]和A[mid,N-1]；那么递归函数就可以这样写了：
void merge_sort(int a[], int start, int end, int temp[])
{
if (start < end)
{
int mid =(start + end)/2;
merge_sort(a, start, mid, temp);
merge_sort(a, mid+1, end, temp);
merge(a, start, mid, end, temp);
}
}
最后再设一个总的归并调用函数；
bool MergeSort(int a[], int n)
{
int *p = new int[n];
if (p == NULL)
return false;
merge_sort(a, 0, n - 1, p);
delete[] p;
return true;
}
主函数在这里：
int _tmain(int argc, _TCHAR* argv[])
{
int a[30] = { 0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20, 21, 22, 23, 24, 25, 26, 27, 28, 29 };
MergeSort(a, 30);
for (auto c : a)
printf("%d ", c);
return 0;
}