原地归并排序是否可以算作是那个神秘的排序算法

Question

归并排序的缺点就是开辟了额外的空间
于是我在网上搜索了一下原地的归并排序是否可以实现, 发现的确有原地归并
因为使用递归所以依然有 logn 的空间复杂度, 为了避免这个开销, 使用循环来进行实现
那么如果使用循环实现原地归并排序,
并且对有序的情况进行优化, 即arr[mid] < arr[mid+1] 直接return, 时间复杂度就应该是 O(n)的了
是不是就是那个神秘的排序算法呢?
以上只是个人猜测

Answer 1

liuyubobobo 2019-06-17 14:54:05

时间复杂度不可能是O(n)：）

arr[mid] < arr[mid+1] 的时候直接return，只能保证在数组有序的时候，进化成O(n)，是带条件的。但是对于一个随机数组，依然是O(nlogn)。

基于比较的排序算法，时间下届是O(nlogn)的：）

计数排序，桶排序，基数排序，是O(n)级别的。但是他们的排序方式，不是基于两个元素之间的比较的。如果有兴趣，可以在网上查一查这三种排序的原理：）

加油！：）

• 提问者 道临 #1

  老师您误会了，在这个节课中你说有一个神秘的算法，平均情况下是nlogn级别，空间复杂度是o（1），同时是稳定排序，在近乎有序的情况是o（n）级别，但是目前没有计算机科学家发现。 我觉得这个我说的这个思路满足上面的条件。

• liuyubobobo 回复 提问者 道临 #2

  大赞，我没有仔细研究过原地归并，不很确定他的稳定性。但如果看其他指标的话，确实是满足的：）

• unknown花名 回复 提问者 道临 #3

  我看了一下它merge的思想，似乎不稳定

点开查看后面1条评论