归并排序是我们研究的最后一种排序了，那什么是归并排序呢？

我们之前在力扣上面刷过一个题目，就是合并两个有序数组，其实也是和这个是一个思想借用第三

个数组，然后将第三个数组拷贝给a数组，这样就实现了排序，接下来，我给大家展示一下归并排序的完整过程， 这个动图很好的展现了归并的思想，但是我们首先是让左区间有序，然后让右区间有序，最后再归并，所以我们需要先将a数组分为两组，然后继续划分，将左区间的左右两个区间有序，再继续划分，直到这个数组只有一个数据，就可以返回了，怎么样，这个思想是不是很熟悉，对，就是递归，我们又用到递归了，上面这幅动图虽然很好的展示了归并，但是没有很好的展示划分的过程，显然这时递归的归过程。

细节--区间划分

假如mid是begin+end除以二，那么这个mid有时候并不公平，而如果要划分为两个区间的话，那么就有两种分法：

但是这两种分法有一个是不行的，我们来看一下第一种分法 

第一种分法是不是好像进入了死循环一样，这是因为[2  3]这个区间是 【偶数   偶数+1】那么他们的mid一定是偶数，到时候分出来左区间是乱七八糟的数，而右边是偶数和偶数+1，那么就会一直这样死循环下去，所以我们只能选择第二种分法，那么为什么呢，我们看一下他的流程 

这个红框框里面就是这个分法里面的好处，不会让死循环进行下去。这个细节是很重要的，我们稍不留神就会被带进坑里，并且有点难发现。

代码展示

//归并排序void _MergeSort(int* a, int* tmp, int begin, int end)
{if (begin >= end){return;}int mid = (begin + end) / 2;//[begin  mid][mid + 1  end]_MergeSort(a, tmp, begin, mid);_MergeSort(a, tmp, mid + 1, end);int begin1 = begin;int end1 = mid;int begin2 = mid + 1;int end2 = end;int i = begin;while (begin1 <= end1 && begin2 <= end2){if (a[begin1] < a[begin2]){tmp[i++] = a[begin1++];}else{tmp[i++] = a[begin2++];}}//第一个数组没有全部进tmp数组while (begin1 <= end1){tmp[i++] = a[begin1++];}//第二个没进while (begin2 <= end2){tmp[i++] = a[begin2++];}memcpy(a + begin, tmp + begin, (end - begin + 1) * sizeof(int));}void MergeSort(int* a, int n)
{int* tmp = (int*)malloc(sizeof(int) * n);if (tmp == NULL){perror("malloc fail!");return;}_MergeSort(a, tmp, 0, n - 1);
}