merge sort为什么递归到只剩1个或0个？如果递归到只剩2个呢

如果递归到只剩2个元素，会降低空间复杂度吗

两个元素可以直接比较大小，其结果只有  执行swap  或者  什么都不做。
时间空间复杂度都是不变的，给楼主画了一个递归调用的图，递归其实是向下分层，计算出最底层后再计算倒数第2层，然后倒数第3层，以此类推。
（不知道咋上传照片。。。相册不能使用，可能因为是新手吧。。。只能上传附件了）

每一层的元素个数都是O(n)，所以也就决定了总的空间复杂度是O(n)。
每一层的时间复杂度都是O(n)，总共有Logn层，所以时间复杂度是Logn * O(n) = O(nlogn)
两个元素直接返回，相当于去掉了倒数第一层，这样空间复杂度不变，时间复杂度为(Logn - 1) * O(n) = O(nlogn) 还是和原来一样。

Big O的定義是function裏面的dominating terms

n元素和n-1元素大家的dominating terms都是n

可以，big O 复杂度不影响

楼主可以了解下 timsort，很多语言的内置 sort 都在用

只剩两个，那两个怎么排序

fightingPhD 发表于 2022-1-26 16:12
只剩两个，那两个怎么排序

不调函数，排序后直接返回排序的结果。

林林路 发表于 2022-01-26 13:30:16
不调函数，排序后直接返回排序的结果。

两个元素谁大谁小不知道，剩到两个可以用其他方法排序，再merge