归并排序算法

归并排序算法

主要思想：分治，但与快速排序有些不同，快速排序是先调整范围再递归左右两边，归并是先递归再归并左右两边

步骤

确定分界点mid=(l+r)/2递归排序left、right归并，合二为一

与快排的不同：快排的分界点是元素，归并的分界点是中间位置

归并排序是稳定的，快排是不稳定的，不过没什么用，可以修改快排使之稳定，只要将每个元素都不同就可以，例如ai变为

时间复杂度：
nlogn
归并排序第三步是O(n)，因为第一个指针只扫描前一半，第二个指针只扫描右一半，每个元素只会被比较一次

n除logn次变为1，所以功logn层