sorting - 给定 O(n) 的存储空间，您对 {1,2,...n^2) 范围内的 n 个元素进行排序的速度有多快？

Question

我正在考虑使用计数排序。但我不认为这是答案，因为在本例中 k 是 n^2。所以排序时间为 O(n+n^2)。我还认为这会超出存储限制。

有什么想法吗？

谢谢。

Answer 1

您可以使用 bottom-up merge sort来实现这一点，其运行时间为 O(n log n)，不需要额外的空间(因为它是就地的)。