algorithm - O(nlogn) 就地排序算法

Question

这道题是我计算机科学概论期中考试的准备题。

There exists an algorithm which can find the kth element in a list in O(n) time, and suppose that it is in place. Using this algorithm, write an in place sorting algorithm that runs in worst case time O(n*log(n)), and prove that it does. Given that this algorithm exists, why is mergesort still used?

我假设我必须编写某种替代形式的快速排序算法，它的最坏情况为 O(n^2)，因为合并排序不是就地算法。让我感到困惑的是给定的算法来查找列表中的第 k 个元素。遍历数组元素的简单循环迭代不是 O(n) 算法吗？

如果提供的算法在执行时间上没有任何改变，那么它如何能对排序算法的运行时间产生任何影响？我看不出如何与快速排序、插入排序或选择排序一起使用，它可以将最坏的情况降低到 O(nlogn)。感谢任何输入!

Answer 1

检查 wiki ，即“按排序选择”部分:

Similarly, given a median-selection algorithm or general selection algorithm applied to find the median, one can use it as a pivot strategy in Quicksort, obtaining a sorting algorithm. If the selection algorithm is optimal, meaning O(n), then the resulting sorting algorithm is optimal, meaning O(n log n). The median is the best pivot for sorting, as it evenly divides the data, and thus guarantees optimal sorting, assuming the selection algorithm is optimal. A sorting analog to median of medians exists, using the pivot strategy (approximate median) in Quicksort, and similarly yields an optimal Quicksort.

为什么合并排序在某些情况下优于快速排序的简短回答是 it is stable (而快速排序不是)。