最坏情况下的数组排序w（n）在前半部分元素小于另一半时起作用？

Question

这是一个理论问题，所以假设需要花费不变的时间来比较array中的elements。

我们得到了array，其elments的前半部分小于另一半。没有东西被排序。它会工作排序在最坏的情况下运行时O(n)还是没有办法？

我认为它不会工作，因为排序前半部分需要O((n/2)*log(n/2))时间，另一半相同。总共这将是O(n*log(n/2))所以仍然O(n*logn)？ 这是对还是错？如果可能的话，请解释我。

Answer 1

你说的没错，在这种情况下你必须n*log(n/2) = n*(log(n) - log(2)) = n*log(n) - n*log(2)这是O(n*log(n))

Answer 2

如果这是真的，你会发现一个革命性的排序方法：以N个元素与N个虚设元素进行排序，追加大的值，按时间排序O（N）并丢弃附加的元素。