归并排序

介绍

归并排序和快速排序一样，都是基于分治思想的应用。
通过递归，不断将原数列分为两个数列，然后再分别使其有序，最后通过归并将两个有序子数列合并为新的有序数列。
值得注意的是，与快速排序不同，归并排序是稳定的。

代码实现

void merge_sort(int a[], int l, int r)
{
        if (l >= r) return;//判断区间数据个数，为1则返回
        int  tmp[100001];//创建临时数组
        int mid = l + r >> 1;
    	merge_sort(a, l, mid);
    	merge_sort(a, mid + 1, r);
    	int k = 0, i = l, j = mid + 1;//建立双指针
    	while (i <= mid && j <= r)//其中一指针遍历至结尾则终止
                if (a[i] <= a[j]) tmp[k++] = a[i++];//对比数据，谁小先加谁
                else tmp[k++] = a[j++];
    	while(i<=mid) tmp[k++] = a[i++];
    	while(j<=r) tmp[k++] = a[j++];//将剩余数据依次放入
    	for (i = l, j = 0; i <= r; i++, j++) a[i] = tmp[j];//将排好的数据放回原数组
}

思路分析

void merge_sort(int a[], int l, int r)
{
        if (l >= r) return;//判断区间数据个数，为1则返回
        int  tmp[100001];//创建临时数组
        int mid = l + r >> 1;
    	merge_sort(a, l, mid);
    	merge_sort(a, mid + 1, r);

和快速排序先排序后递归不同，归并排序是先递归，无限细分，重点在于回溯时的归并，当递归到数组区间内只有1个数据时，肯定是有序的，经过归并后返回的数组肯定也是有序的，所以我们这里假设这个函数已经能够实现目的，将一个数组分为两部分然后分别排序，只需要用标记区间的起始位置和结束位置，而两个区间的分界就是mid，而归并的时候我们需要一个临时存放数据的临时数组tmp[]。

int k = 0, i = l, j = mid + 1;//建立双指针
while (i <= mid && j <= r)//其中一指针遍历至结尾则终止
        if (a[i] <= a[j]) tmp[k++] = a[i++];//对比数据，谁小先加谁
        else tmp[k++] = a[j++];

这里便是整个算法最关键的地方：数组的归并。

首先，我们知道，两个区间已经分别有序，而第一个区间起点便是本次函数传入的起点l，终点为中值mid，第二个区间起点为mid+1，终点为函数传入的终点参数r。

我们创建双指针li和j，初始位置分别指向两个取件的起始位置，不断互相比较，值更小的放入数组然后往后遍历，这样就能实现整个数组的归并，值得注意的是，我们的判断条件为if(a[i]<=a[j])，这样，就能保证同样大小的数据按照原先的顺序依次进入临时数组，实现归并排序的稳定性。

最终，当其中一个指针遍历到区间结尾时，结束循环。

while(i<=mid) tmp[k++] = a[i++];
while(j<=r) tmp[k++] = a[j++];//将剩余数据依次放入
for (i = l, j = 0; i <= r; i++, j++) a[i] = tmp[j];//将排好的数据放回原数组

当然，我们还需要将另外一个区间剩下的数据依次挤入临时数组，实现最终的排序，那我们就通过比较指针和终点的值来实现。

最后将排好的数据从临时数组中依次赋给原数组。

至此，我们完成了整个归并排序算法的闭环，完成了功能的实现。

结尾

归并排序和快速排序都是分治思想的体现，他们的思路不仅仅能拿来排序，也能解决一些具体问题，具体选择哪一种算法，就要依靠你细致入微的观察，结合题目的特性。

最后，归并排序和快速排序的时间复杂度一样，都是O(nlogn)。

以上便是对归并排序的介绍，本文由凉茶coltea撰写，思路来自AcWing，大佬yxc的课程。