1.归并排序
简介
归并排序基于分治思想将数组分段排序后合并，时间复杂度在最优、最坏与平均情况下均为O(n log n)
，空间复杂度为 O(n)
。
归并排序可以只使用 O(1)
的辅助空间，但为便捷通常使用与原数组等长的辅助数组。
归并排序最核心的部分是合并（merge）过程：将两个有序的数组 a[i] 和 b[j] 合并为一个有序数组 c[k]。
标签：归并,进阶,复杂度,元素,合并,算法,数组,排序 From： https://blog.csdn.net/Michael888888ha/article/details/139783460从左往右枚举
a[i]和b[j]，找出最小的值并放入数组c[k]；重复上述过程直到a[i]和b[j]有一个为空时，将另一个数组剩下的元素放入c[k]。为保证排序的稳定性，前段首元素小于或等于后段首元素时（
a[i] <= b[j]）而非小于时（a[i] < b[j]