前言
排序(Sorting) 是计算机程序设计中的一种重要操作，它的功能是将一个数据元素（或记录）的任意序列，重新排列成一个关键字有序的序列。所谓排序，就是使一串记录，按照其中的某个或某些关键字的大小，递增或递减的排列起来的操作。
排序算法，就是如何使得记录按照要求排列的方法。排序算法在很多领域得到相当地重视，尤其是在大量数据的处理方面。一个优秀的算法可以节省大量的资源。
简介
所谓排序算法，即通过特定的算法因式将一组或多组数据按照既定模式进行重新排序。这种新序列遵循着一定的规则，体现出一定的规律，因此，经处理后的数据便于筛选和计算，大大提高了计算效率。对于一个排序算法的优劣，我们需要从它的时间复杂度、空间复杂度和稳定性三个方面来考虑。什么叫稳定性呢？即当两个相同的元素同时出现于某个序列之中，则经过一定的排序算法之后，两者在排序前后的相对位置不发生变化。换言之，即便是两个完全相同的元素，它们在排序过程中也是各有区别的。
本篇文章讲述的是排序算法中的归并排序。（用升序进行讲解）
归并排序（MERGE-SORT）是建立在归并操作上的⼀种有效的排序算法,该算法是采用分治法（Divide and Conquer）的一个非常典型的应用。
基本思想
归并排序的基本思想就是将已有序的子序列合并，得到完全有序的序列。通俗来讲就是我们需要通过有序的两个数组合并成一个新的有序的数组，对于合并两个有序数组有一道算法题，感兴趣的可以做一做（地址：力扣 ： 88.合并两个有序数组）。若将两个有序表合并成一个有序表，称为二路归并。
我们已经知道归并排序算法的原理，那么我们先来思考一个问题：
我们本来就是要对一个无序的序列进行排序，那我们该怎么从中找到两个有序的序列呢？
是不是有点迷茫了，其实换一个角度想，这个问题十分容易解决。当我们一个序列中只有一个元素的时候，它是不是就一定为有序的了。因此，我们的问题就得以解决了，第一步就是分割，将序列中的所有元素分割成一个一个单独的序列，然后对其两两进行合并。这就是归并排序算法的核心，具体是怎么操作的，通过下图大家可以有更清晰的了解：
通过分割，我们便可以得到由需要排序的序列所分成的所有有序序列，接下来我们只需要对其一一进行合并即可完成排序。对于合并就是简单的合并两个有序序列。如下图所示：
那么我们该怎么实现这一整个过程呢？我们可以使用递归来完成我们的目标。每一次的递归都先将一整个序列分为两半，直到序列中只剩下一个元素，此时进行合并即可。我们可以把合并出来新的有序序列存放于一个临时序列中，待合并完成后再将临时序列中的元素一一赋值给原序列中相对应的位置即可。
合并的具体思路：定义三个指针分别指向第一、二个序列和临时序列的第一个元素，然后对指针指向的元素进行比较，将较小的那一个元素添加到临时序列中，随即将对应的指针往后移动一位，直到指向第一个序列或第二个序列的指针走完，因为两个序列都是有序的，所以此时将没有走完的指针所指向的位置的后面所有元素都放入临时序列中即可。
代码实现
下面让我们来看一下如何使用递归来实现我们的归并排序。我们可以通过定义两个指针 left 、right 来判断此时序列中元素的个数和该子序列在整个序列中的具体位置，然后不断将其从中间进行分割，直到只有一个元素，此时退出递归，回到上一层，进行合并即可。合并的过程就是对 left 、right 通过中间值 mid 分为的两个序列进行合并。
代码如下：
void Merge_Sort(vector<int>& a, int left, int right)
{
//当l >= r，也就是数组中只有一个元素时结束递归，开始进行合并
if (left >= right)
{
return;
}
int mid = (left + right) / 2;
//此处的区间范围注意不能为mid - 1,下面为mid，因为当l == 0,right == 1时会无限递归下去陷入死循环
Merge_Sort(a, left, mid);
Merge_Sort(a, mid + 1, right);
//分割结束，开始合并。此时两个有序的区间为[left, mid]和[mid + 1, right]
int begin1 = left, end1 = mid;
int begin2 = mid + 1, end2 = right;
int index = 0;
//用一个临时数组来记录合并后的新数组
vector<int> tmp(right - left + 1);
//当两个数组中有一个的元素都被放入tmp中后结束比较
while (begin1 <= end1 && begin2 <= end2)
{
if (a[begin1] < a[begin2])
{
tmp[index++] = a[begin1++];
}
else
{
tmp[index++] = a[begin2++];
}
}
//将还有剩余元素的数组中的所有元素直接放在tmp中
while (begin1 <= end1)
{
tmp[index++] = a[begin1++];
}
while (begin2 <= end2)
{
tmp[index++] = a[begin2++];
}
//将临时数组中的值重新赋给原数组中对应的位置
for (int i = right; i >= left; i--)
{
a[i] = tmp[--index];
}
}
总结
1.时空复杂度
归并排序的时间复杂度取决于两个点，一个是递归，一个是合并有序序列，对于合并有序序列的时间复杂度为O（N），我们的每一次递归都是将序列分为两部分，因此这是一个二叉树递归，其时间复杂度为O（NlogN），至于具体的计算过程这里不再赘述，感兴趣的可以去了解一下。因此归并排序的整个时间复杂度为O（NlogN）。
归并排序的空间复杂度就是那个临时的数组和递归时压入栈的数据占用的空间：n + logn；所以空间复杂度为: O(n)。
归并排序：
时间复杂度：O（NlogN）
空间复杂度：O(n)
2.稳定性
在排序算法中，我们不光要关注算法的时空复杂度，还在看看算法的稳定性，什么是稳定性呢？
稳定性是假定在待排序的记录序列中，存在多个具有相同的关键字的记录，若经过排序，这些记录的相对次序保持不变，即在原序列中，r[i]=r[j]，且r[i]在r[j]之前，而在排序后的序列中，r[i]仍在r[j]之前，则称这种排序算法是稳定的；否则称为不稳定的。
对于归并排序，在进行元素比较和交换时，若两个元素大小相等则不必刻意交换位置，因此该算法不会破坏序列的稳定性，即归并排序也是稳定的排序算法。
归并排序 ： 稳定
尾声
若有纰漏或不足之处欢迎大家在评论区留言或者私信，同时也欢迎各位一起探讨学习。感谢您的观看！