归并排序（Merge Sort）算法介绍
一、引言
归并是一种常见的算法思想，在许多领域都有广泛的应用。归并排序的主要目的是将两个已排序的序列合并成一个有序的序列。
二、算法思想
对于一个非有序的序列，可以将其拆分成两个非有序的序列，然后分别调用归并排序，再对两个有序的序列进行合并。整个算法的执行过程可以用 mergeSort(a[], l, r) 描述，代表当前待排序数组 a，左区间下标 l，右区间下标 r，分以下几步：
- 计算中点：
mid = (l + r) / 2； - 递归调用：
mergeSort(a[], l, mid)和mergeSort(a[], mid + 1, r)； - 合并：将第二步中两个有序数组进行有序合并，再存储到
a[l:r]。
调用 mergeSort(a[], 0, n-1) 就能得到整个数组的排序结果。
三、动图演示
归并排序完整排序过程如下图所示：
演示说明：
- 首先将 8 个元素分成 4 个元素，再将 4 个元素分成 2 个元素。
- 比较这 2 个元素的值，使其在自己的原地数组内有序。
- 然后两个 2 个元素的数组合并变成 4 个元素的升序数组。
- 最后将两个 4 个元素的数组归并变成 8 个元素的升序数组。
四、算法分析
1. 时间复杂度
假设「比较」和「赋值」的时间复杂度为 O(1)。归并排序的时间复杂度为 O(nlog2n)，因为归并过程类似于一颗二叉树的构建过程，次数是二叉树的高度，即 log2n。
2. 空间复杂度
归并排序在归并过程中需要额外的一个辅助数组，最大长度为原数组长度，所以空间复杂度为 O(n)。
五、算法的优点
- 稳定性：归并排序是一种稳定的排序算法，即相同元素的相对顺序保持不变。
- 可扩展性：归并排序可以很容易地扩展到并行计算环境中，通过并行归并来提高排序效率。
六、算法的缺点
- 额外空间：归并排序需要使用额外的辅助空间来存储合并后的结果，这对于内存受限的情况可能是一个问题。
- 复杂性：归并排序的实现相对复杂，相比于其它一些简单的排序算法。
七、优化方案
归并排序在众多排序算法中效率较高，时间复杂度为 O(nlog2n)。但是，申请辅助数组内存空间带来的时间消耗比较大。优化方案是使用一个与给定元素个数相同大小的数组，作为函数传参传进去，所有辅助数组的操作都在这个传参数组上进行操作，避免内存的频繁申请和释放。