递归归并排序1.复杂度分析1.时间复杂度拆分每层递归把数组二分一共log2n(2为底数层合并每一层所有合并操作总操作量是n总O(nlogn)最好、最坏、平均都是O(nlogn)不受原始数组有序无序影响2.空间复杂度需要临时数组存合并结果O(n)递归调用栈深度是logn可以忽略主要开销是辅助数组3.稳定性稳定排序合并时arr[i]arr[j]相等元素保留原来先后顺序。2.递归要点1.递归出口条件leftright区间长度为1直接返回不再递归。2.二分中点mid(leftright)//2,注意右区间是mid1,避免重复。3.先递归排序左右之后才执行合并。4.归并排序不是原地排序需要额外空间零碎while循环左右都还有元素的时候两两比较小的放进临时数组bwhile退出后必须有一段已经取完剩下另一端直接整体复制无需再比较im左区间取完原数组a右区间剩下的元素直接复制到临时数组belse:(jr):右区间全部取完原数组a左区间剩下的元素直接复制到临时数组b此时临时数组b[l~r]已经是完全有序最后拷贝回原数组a中