1.归并排序基本信息

1.基本原理

归并排序是建立在归并操作上的一种有效的排序算法，该算法是采用分治法的一个非常典型的应用。

将已有序的子序列合并，得到完全有序的序列；

即先使每个子序列有序，再使子序列段间有序。

分解：将数组分割成两个数组，再分别将两个数组又细分成2个数组，直到，最后每个数组都是一个元素，这时将该单元素数组看为有序数组

合并：将分割的有序数组进行排序，排成有序数组后继续为上一个分割它的数组合并，直到数组被合并成原来的数组，此时已经排好序了

2.优缺点

和选择排序一样，归并排序的性能不受输入数据的影响，但表现比选择排序好的多，因为始终都是O(n log n）的时间复杂度。代价是需要额外的内存空间。归并排序是建立在归并操作上的一种有效的排序算法。该算法是采用分治法一个非常典型的应用
 

3.动图理解

4.复杂度

1.时间复杂度
归并排序把集合进行层层拆半分组。如果集合长度为n，那么拆半的层数就是logn，每一层进行归并操作的运算量是n。所以，归并排序的时间复杂度等于每一层的运算量×层级数，即O(nlogn)。

2.空间复杂度
归并排序是需要用到额外空间的，但是每次归并所创建的额外空间都会随着方法结束而释放，因此单次归并操作开辟的最大空间是n。所以，归并排序的空间复杂度是O(n)。

2.归并排序的思路

先用这张图来大概展示一下思路，下面将会细讲

1.最基础操作（合并）

即：将已有序的子序列合并，得到完全有序的序列；

如果有两个已经排序好的数组；
我们要把这两个数组合并；

1.我们先把俩数组合并成一个数组，这个很简单；

但是合并之后的数组可能并不是一个特别有序的数组，那么此时我们就要给他排序；

2.我们把两个数组排序一下返回一个完全有序的序列

我们用 i 来表示数组A中的第一个元素；
用 j 来表示数组B中的第一个元素；
用 k 来表示新数组也就是待排序的数组的第一个元素；

判断 i 和 j的大小；
如果i<j，那么就让k=i；i++，k++；
如果i>j，那么就让k=j；j++，k++；

假设i<j，那么此时新数组的第一个数字已经排进去了，i++，说明此时i指向了A的第2个元素，而此时j并没有动，仍指向B第一个元素。这时候再次比较ij大小，以此类推，直到某个数组全部元素都清空，我们此时直接把另一个数组的元素并入其中即可。

好了，原理理清，我们开始整理代码思路

我们定义一个merge函数接受1个数组arr，以及待合并子序列的左边界left、中间位置mid和右边界right作为参数。函数的目标是将r中[left, mid]和[mid+1, right]两个有序子序列合并到数组temp中。

具体的合并过程如下：

1. 定义一个数组temp暂时储存有序数组。
2. 定义三个指针i、j和k，分别指向左子序列的起始位置left，右子序列的起始位置mid+1，以及合并后的数组temp的起始位置left。
3. 当i指针和j指针都在对应的子序列内时，比较arr[i]和arr[j]的大小，并将较小的元素放入temp[k]中。移动指针i或j，以及k，继续循环比较并填充temp数组。
4. 若左子序列有剩余元素，将剩余元素依次放入temp数组中。若右子序列有剩余元素，将剩余元素依次放入temp数组中。
5. 将k返回最开始的位置，遍历temp数组存入arr数组中
6. 返回0表示合并过程完成。

来人，上代码！

void merge(int arr[], int left, int mid, int right) {
	int temp[100];
	int i = left, j = mid + 1;
	int k = left;
	while (i <= mid && j <= right) {
		if (arr[i] < arr[j]) {
			temp[k++] = arr[i++];
		}
		else {
			temp[k++] = arr[j++];
		}
	}
	while (i <= mid) 
		temp[k++] = arr[i++];
	while (j <= right) 
		temp[k++] = arr[j++];
	k = left;
	while (k <= right) {
		arr[k] = temp[k];
		k++;
	}

}

2.分治法扩大可操作范围

下来开始第二个操作：分！！！

上方我们合并的时候用的是有序数组来排，但是通常我们要的是给乱序数组排序。

这就要用到一个叫做分治法的一个思想；
怎么回事呢；
就是把目标数组分成两半，去执行上面的排序功能，

当我们发现分割后的两个小数组也不满足我排序功能的条件啊！

哎，那我就把小数组都再次分成两半，分成小小数组，再去归并排序；

啊？还不满足，那就再给我分！给我分分分分！！

最后分成一堆就剩一个元素的数组，一定满足有序的条件了吧！

此时我们再把这些小小小数组（数字）给合并，根据我们上面的艰苦奋斗，发现合并出来肯定有序，直到合并得就剩一个，那不就完成了吗！

那么下来便是代码思路：

具体的分割过程如下：

1. 首先判断left是否小于right，如果不满足这个条件，则说明当前子序列只有一个元素或为空，无需再进行拆分和合并操作，直接返回。
2. 计算出中间位置mid=(left+right)/2。
3. 通过递归调用mergesort函数，将左半部分的子序列继续拆分并进行排序（从left到mid）。
4. 通过递归调用mergesort函数，将右半部分的子序列继续拆分并进行排序（从mid+1到right）。
5. 调用merge函数将左半部分和右半部分的子序列进行合并操作。

在mergesort函数中，通过不断地二分拆分子序列并进行合并操作，最终完成整个序列的排序。

下来便是代码：

void mergesort(int arr[], int left, int right) {
    if (left < right) {
        int mid = (left + right) / 2;
        merge_sort(arr, left, mid);
        merge_sort(arr, mid + 1, right);
        merge(arr, left, mid, right);
    }
}

3.代码实现

有了上面两个操作的，归并排序就已经完成了

我们只需要引用一次mergesort函数即可通过函数本身来完成分与治两个方向

下来便是归排函数的完整代码

void merge(int arr[], int left, int mid, int right) {
	int temp[100];
	int i = left, j = mid + 1;
	int k = left;
	while (i <= mid && j <= right) {
		if (arr[i] < arr[j]) {
			temp[k++] = arr[i++];
		}
		else {
			temp[k++] = arr[j++];
		}
	}
	while (i <= mid) 
		temp[k++] = arr[i++];
	while (j <= right) 
		temp[k++] = arr[j++];
	k = left;
	while (k <= right) {
		arr[k] = temp[k];
		k++;
	}
}
void merge_sort(int arr[], int left, int right) {
    if (left < right) {
        int mid = (left + right) / 2;
        merge_sort(arr, left, mid);
        merge_sort(arr, mid + 1, right);
        merge(arr, left, mid, right);
    }
}

归并排序三大特点：

在“递”的过程中，对数组均等一分为二，再将子数组，一分为二;

在“归”的过程中，将这两个有序的子数组合并成一个有序的子数组；

递归：

递归的结束返回永远是最小子问题的解

递归调用就是普通函数调用，并无本质区别（每次调用有自己独立的栈空间）

用递归思路解决问题，一定要时刻提醒自己原问题是什么，那么子问题就是什么！