数据结构：归并排序

直观感受请点击视频观看：
参考视频

归并排序：

是创建在归并 *** 作上的一种有效的排序算法。

算法是采用分治法（Divide and Conquer）的一个非常典型的应用，且各层分治递归可以同时进行。

归并排序思路简单，速度仅次于快速排序，为稳定外部排序算法，一般用于对总体无序，但是各子项相对有序的数列。

基本思想：采取分治，归并的思想，主要采取三个步骤：
1：分解：将序列中待排序数列分为若干个组
2：将若干个组合并，每次比较左右数列头部谁更小（更大），移动进新数列，再比较两组数据的头部，保证数列有序（重点）
3：重复第2步 *** 作，直到只剩下一组数列，排序完成
分解如下图：

合并优化：并不需要分解为单个元素，只要待排序元素<=2个就可以排序了

代码参考：

//递归思想实现归并排序
void merge_sort(int *num,int l,int r){  //那段空间
	//1.考虑边界条件：出口
	if(r - l <= 1){ //两个及两个以内的元素，整个待排序的空间r-l
		if(r - l == 1 && num[r] < num[l]) {
			swap(num[r],num[l]);
		}
		return ;
	}
	//回溯：二路取中法
	int mid = (l + r) >> 1;
	merge_sort(num, l ,mid);//左半段
	merge_sort(num, mid + 1, r);//右半段
	int *temp = (int *)malloc(sizeof(int)*(r - l + 1));  //合并两个有序的数组
	int p1 = l,p2 = mid + 1,k = 0;//分别为第一第二段头元素位置，和当前temp的位置
	while(p1 <= mid ||p2 <= r){   //还有待排元素
		if(p2 > r||(p1 <= mid && num[p1] <= num[p2])){ //第二段没元素了
			temp[k++] = num[p1++];//插入左半段的元素
		} else {
			temp[k++] = num[p2++];//插入右 u半段的元素
		}
	}
	memcpy(num + l，temp,sizeof(int) * (r - l + 1))；//内存拷贝，拷贝到原数组
	free(temp);
	return ;
}