一、归并排序的原理

如果要排序一个数组，我们先把数组从中间分成前后两部分，然后对前后两部分分别排序，再将排好序的两部分合并在一起，这样整个数组就都有序了。
image.png

其中，合并过程如下图所示：
申请一个临时数组 tmp，大小与 A[p…r]相同。我们用两个游标 i 和 j，分别指向 A[p…q]和 A[q+1…r]的第一个元素。比较这两个元素 A[i]和 A[j]，如果 A[i]<=A[j]，我们就把 A[i]放入到临时数组 tmp，并且 i 后移一位，否则将 A[j]放入到数组 tmp，j 后移一位。
image.png
PS：可以使用哨兵来简化代码

二、归并排序的特点

1、归并排序是稳定的排序算法
2、归并排序的时间复杂度：O(nLogn)
3、归并排序的空间复杂度：O(n)