今天，小编继续带大家学习排序算法，这次我们一起来学习归并排序的递归算法，多多点赞支持博主，速更非递归算法哦！
目录
归并算法的实现与快排类似，都是采用了分治递归的思路。
它的时间复杂度也是O(n*logn)。
但不一样的是，快排是从排序最上层开始一点点递归到最底层；而归并是通过递归直接到最底层，从最底层开始一步步返回到最上层。
我们拿int类型的排序举例，归并来到最底层之后，应该是两个数字一组进行比较，从小到大排好，之后回到上一层，再这样排，直到到达最上层。
那有人会问了，这样子每一层都排好后返回上层不久又乱了，又要重新排了么。哎，这就要说我们归并排序的与众不同了。
以升序为例，归并是基于两个数组都是升序的基础上，记录两个指针分别指向两个数组的头，两指针所代表的数相比，小的顺次放入新数组，该指针指向下一个下标，循环这个比较的过程，直到其中一个指针指到尾，另一个数组全部放入新数组即可。
用图画来表示就是如下步骤：
void mergesort(int* a, int left,int right,int n);//归并排序
void _mergesort(int* a, int left, int right, int *tmp);//归并排序的子函数
void mergesort(int* a, int left,int right,int n)//归并排序
{
int* tmp = (int*)malloc(sizeof(int) * n);//创建一个动态数组，存放归并后的有序数组
_mergesort(a, left, right, tmp);
}
void _mergesort(int* a, int left, int right, int *tmp)//归并的子排序
{
if (left >= right) return;//递归返回条件
int mid = (left + right) >> 1;
//分治递归思想
_mergesort(a, left, mid, tmp);
_mergesort(a, mid + 1, right, tmp);
//归并
int begin1 = left, begin2 = mid + 1,i_tmp=left;//注意要专门设一个变量存放tmp数组的下标
while (begin1 <= mid && begin2 <= right)//归并继续条件
{
if (a[begin1] < a[begin2]) tmp[i_tmp++]= a[begin1++];
else tmp[i_tmp++] = a[begin2++];
}
//归并结束后可能会有一个数组的数还未完全放入tmp中
while (begin1 <= mid) tmp[i_tmp++] = a[begin1++];
while (begin2 <= mid) tmp[i_tmp++] = a[begin2++];
//将tmp数组中的数放入原数组(a)中
for (int i = left; i <= right; i++)
{
a[i] = tmp[i];
}
}值得注意的是：我们需要一个子函数来进行递归，是因为归并算法要创建一个临时数组存放每次比较完的数，而因为是递归的方法，递归多少次就要创建多少个临时数组，势必会有内存的占用和浪费，因此，采用主归并函数来创建一次临时数组，子函数来接收这个临时数组，就能做到每次递归子函数时都是调用这一个临时数组了。
但是，之前快排的时候讲过，一旦递归调用次数过多，会导致栈溢出，那么如果归并也能采用非递归的算法，就会节省很多空间而且创建的临时数组也能直接在归并函数中使用，不用再创建子函数了。
因此，多多点赞支持博主，下一篇就会速更归并排序算法的非递归实现哦！
感谢点赞支持