一、基本思想

先使每个子序列有序，再使子序列段间有序。若将两个有序表合并成一个有序表，称为二路归并

二、动图演示

分解图：

1. 简单分析一下，上图是通过将原有的序列【10 6 7 1 3 9 4 2】分割成两部分，然后对子区间再继续进行划分，再分割成两部分，一直划分直到区间的数据个数小于等于1为止，这就相当于是一个【递归】的过程，观察上半部分图，就是一棵二叉树。
2. 分解完成开始合并，原序列需要左区间有序，右区间有序，才可以对左右区间进行一个归并，因此从单个的小区间开始，向上回调进行归并层层回调上来后，左右区间再进行一个归并，最后得到一个有序的序列，这类似二叉树中的后序遍历。

三、递归方式实现

3.1代码演示及解读

话不多少，先上代码

//归并排序 时间复杂度O(n*logn)
//空间复杂度 O(n)

void _MergeSort(int* a, int begin, int end, int* tmp)
{
	if (begin >= end) {
		return;
	}
	int mid = (begin + end) / 2;
	//[begin, mid] [mid+1, end] 递归让子区间有序
	_MergeSort(a, begin, mid, tmp);
	_MergeSort(a, mid + 1, end, tmp);

	//归并[begin,mid],[mid+1,end]
	int begin1 = begin, end1 = mid;

	int begin2 = mid + 1, end2 = end;
	int i = begin;
	while (begin1 <= end1 && begin2 <= end2) {
		//等同于尾插
		if (a[begin1] <= a[begin2]) {
			tmp[i++] = a[begin1++];
		}
		else
		{
			tmp[i++] = a[begin2++];
		}
	}
	//如果前半组没走完
	while (begin1 <= end1) {
		tmp[i++] = a[begin1++];
	}
	//如果后半组没走完
	while (begin2 <= end2) {
		tmp[i++] = a[begin2++];
	}
	memcpy(a + begin, tmp + begin, sizeof(int) * (end - begin + 1));
}
void MergeSort(int *a,int n) {
	//动态开辟内存空间
	int* tmp = (int*)malloc(sizeof(int)*n);
	if (tmp==NULL) {
		perror("malloc fail");
	}
	_MergeSort(a,0,n-1,tmp);
	//释放内存空间
	free(tmp);
	tmp = NULL;
}

代码解读：

1. 首先，我们通过图解可以发现，归并排序有两个过程，一是递归分解，二是合并。因此，我们需要开辟一个数组用来存放临时的数据。
2. 在这里我们用两个函数完成此算法，MergeSort主要是动态开辟内存空间、调用排序函数_MergeSort及内存的释放。归并排序的核心就是_MergeSort
3. _MergeSort函数形参分别代表：待排序数组a,数组a的起始位置begin,末尾end,临时数组tmp。首先递归对原序列进行划分

	//递归出口
	if (begin >= end) {
		return;
	}
	int mid = (begin + end) / 2;
	//[begin, mid] [mid+1, end] 递归让子区间有序
	_MergeSort(a, begin, mid, tmp);
	_MergeSort(a, mid + 1, end, tmp);

~~——————————————————————————–~

1. ① 首先记录左右两个区间的端点值，因为每次划分mid的值都会变化，begin和end的值也会变化，所以我们用四个变量记录两个区间。

   ②当一个区间的左右子区间都递归完成后，就要对这两个区间进行一个归并的逻辑，定义遍历【i】用来遍历tmp这个临时数组，因为tmp会一直存放数据，因此在下一次还要存放数据的时候就要从传进来的begin开始放置，因为begin是在不断变化的

   ③接下去的话就是两个区间的数据不断比较的过程，放在一个while循环里，结束条件就是当一个区间已经遍历完毕之后就退出（begin1 <= end1 && begin2 <= end2这个是循环继续条件，大家一定要分清楚哦），因为当一个区间遍历完后，一个区间的所有数据和另一个区间一定全都比较过了，因此另一个区间剩下来的数据一定是大的那些数，所以在跳出循环后直接将某一段区间中还剩下的数据放在到tmp数组之后就可以了。如果大家对第三条有疑问的，可以参考一种题型《合并两个有序数组》

//归并[begin,mid],[mid+1,end]
	int begin1 = begin, end1 = mid;

	int begin2 = mid + 1, end2 = end;
	int i = begin;
	while (begin1 <= end1 && begin2 <= end2) {
		//等同于尾插
		if (a[begin1] <= a[begin2]) {
			tmp[i++] = a[begin1++];
		}
		else
		{
			tmp[i++] = a[begin2++];
		}
	}
	//如果前半组没走完
	while (begin1 <= end1) {
		tmp[i++] = a[begin1++];
	}
	//如果后半组没走完
	while (begin2 <= end2) {
		tmp[i++] = a[begin2++];
	}

2. 如果说以上的步骤是最核心的一步，那么下面的这句memcpy函数使用memcpy(a + begin, tmp + begin, sizeof(int) * (end - begin + 1));就是最关键的一步，因为每一次归并完后的数据都是存放在tmp临时数组里的，所以我们要将这些数据拷贝回原数组

   因为我们每一次归并完都要往回拷贝，所以每一次数组拷贝的起始位置和拷贝大小都是不一样的，这要根据分解的区间而定，所以我们可以通过每次变更的【begin】和【end】进行一个控制，而对于【end – begin + 1】就是本次需要回拷的数组个数即数组大小。

递归分解图方便理解递归过程：

四、非递归方式实现

4.1非递归思想

其实对于归并的非递归来说有一种很简单的思路，也不需要利用额外的数据结构，只需要使用一个变量控制每次要归并的数据个数，归并排序一般情况下是两两一归并成四、或者四四一归并成八，但是特殊情况我们还需要单独考虑一下
所以我们可以像下面这样去考虑，分为三次归并，首先是一一归并，使一个小区间中的两个数有序；然后两两归并，使一个小区间中的四个数有序；接下去四四归并，也就是使得正确区间有序。每一大组的归并放进一个循环中。但是每次要怎么使得刚好可以一一、两两、四四进行归并呢，这就需要使用到一个【rangeN】的变量来控制每次归并区间的大小了，具体如何控制我们放到代码中讲解

算法分解图：

4.2完整代码演示及解读

void MergeSortNonR(int* a, int n) {
	int* tmp = (int*)malloc(sizeof(int) * n);
	if (tmp == NULL) {
		perror("malloc fail");
	}

	// 归并每组数据个数，从1开始，因为1个认为是有序的，可以直接归并
	int rangeN = 1;
	while (rangeN < n) {//控制归并趟数，1 1-》2；2 2-》4；4 4 -》8；
		for (int i = 0; i < n; i += rangeN * 2) {//控制每一趟要合并的组
			//归并
			int begin1 = i, end1 = i + rangeN - 1;
			int begin2 = i + rangeN, end2 = i + 2 * rangeN - 1;
			
			//越界检测
			printf("[%d,%d][%d,%d]\n", begin1, end1, begin2, end2);
			//只能分组拷贝
			//end1 begin2 end2越界
			if (end1 >= n) {
				break;
			}
			//begin2,end2越界
			else if (begin2 >= n) {
				break;
			}
			//end2越界
			else if (end2 >= n) {
				end2 = n - 1;
			}
			int j = i;
			while (begin1 <= end1 && begin2 <= end2) {
				if (a[begin1] <= a[begin2]) {
					tmp[j++] = a[begin1++];
				}
				else
				{
					tmp[j++] = a[begin2++];
				}
			}
			while (begin1 <= end1) {
				tmp[j++] = a[begin1++];
			}
			while (begin2 <= end2) {
				tmp[j++] = a[begin2++];
			}
			//不修正，部分拷贝
			memcpy(a+i, tmp+i, sizeof(int) * (end2-i+1));
		}
		rangeN *= 2;
	}
	free(tmp);
	tmp = NULL;
}

4.3三种越界情况及解决方案

对于特殊情况，如果不是八的倍数个数据，就会发生不同的越界情况，下面我们看一个例子

从上图可以看出越界有三种情况，我们采用两种办法解决
1：上述代码所用的break方法,这种方法具有局限性，采用这种方法最后拷贝的时候只能归并一组拷贝一组，不能一趟归并完再拷贝
2.修正区间法：通过对越界的区间修改避免越界访问。此方法拷贝的时候既可以局部拷贝，也可以整体拷贝

//修正区间
			//end1 begin2 end2越界
			if (end1 >=n) {
				end1 = n - 1;
				//设置成不存在区间
				begin2 = n;
				end2 = n-1;
			}
			//begin2,end2越界
			else if (begin2>=n) {
				//设置成不存在区间
				begin2 = n;
				end2 = n-1;
			}
			//end2越界
			else if (end2>=n) {
				end2 = n - 1;
			}

完整代码：

void MergeSortNonR(int *a,int n) {
	int* tmp = (int*)malloc(sizeof(int) * n);
	if (tmp == NULL) {
		perror("malloc fail");
	}

	// 归并每组数据个数，从1开始，因为1个认为是有序的，可以直接归并
	int rangeN = 1;
	while (rangeN<n) {//控制归并趟数，1 1-》2；2 2-》4；4 4 -》8；
		for (int i = 0; i < n;i+=rangeN*2) {//控制每一趟要合并的组
			//归并
			int begin1 = i, end1 = i + rangeN - 1;
			int begin2 = i + rangeN, end2 = i + 2 * rangeN - 1;
			//越界检测
			printf("[%d,%d][%d,%d]\n", begin1, end1, begin2, end2);
			//修正区间
			//end1 begin2 end2越界
			if (end1 >=n) {
				end1 = n - 1;
				//不存在区间
				begin2 = n;
				end2 = n-1;
			}
			//begin2,end2越界
			else if (begin2>=n) {
				//不存在区间
				begin2 = n;
				end2 = n-1;
			}
			//end2越界
			else if (end2>=n) {
				end2 = n - 1;
			}
			int j = i;
			while (begin1 <= end1 && begin2 <= end2) {
				if (a[begin1] <= a[begin2]) {
					tmp[j++] = a[begin1++];
				}
				else
				{
					tmp[j++] = a[begin2++];
				}
			}
			while (begin1 <= end1) {
				tmp[j++] = a[begin1++];
			}
			while (begin2 <= end2) {
				tmp[j++] = a[begin2++];
			}
			//部分拷贝
			//memcpy(a+i, tmp+i, sizeof(int) * (end2-i+1));

		}
		//整体拷贝
		memcpy(a,tmp,sizeof(int)*n);
		rangeN *= 2;
	}
	free(tmp);
	tmp = NULL;
}

五、复杂度及稳定性分析

时间复杂度：O(N*logN)
空间复杂度：O(N)
稳定性：稳定
时间复杂度经典O(N*logN)
空间复杂度中开辟了额外数组，空间复杂度为O(N)
稳定性中，有序过程类似于单链表尾插，相等的数，在前面的就插入前面，在后面的就插入后面，所以是稳定的