排序-归并排序

2022-01-22 本文已影响0人习惯水文的前端苏

$\bullet$ 目录

$\bullet$ 时间复杂度

第一次二分，需merge两次，第二次二分，merge四次......故需要合并logn次，每次合并过程是n，故为 $O(n \log_2 n)$

$\bullet$ 空间复杂度

O(n):辅助数组res
$\bullet$ 思路

将待排数组不断二分，直到分出的两个子数组的成员为1个时停止

此时

两个子数组一定有序

则对这两个有序的数组合并成一个有序数组

那么

在最后一次递归中假设分出的数组为[2]、[1]

则合并之后的结果为[1,2]

此时返回上一个递归序中，假设拿到排好的数组[0,3]

则

在当前递归序中，对[1,2]和[0,3]进行合并

结果为[0,1,2,3]

最后将结果copy替换原数组

$\bullet$ 实现