c# - .NET List.Sort 使用 introsort，为什么最坏的情况是 O(n^2)？

Question

List<T>.Sort 的 .NET 文档提到渐近运行时:https://learn.microsoft.com/en-us/dotnet/api/system.collections.generic.list-1.sort?view=netframework-4.7.2

On average, this method is an O(n log n) operation, where n is Count; in the worst case it is an O(n^2) operation.

它还提到它是使用 Array.Sort 实现的，它还有一个运行时声明:https://learn.microsoft.com/en-us/dotnet/api/system.array.sort?view=netframework-4.7.2

For arrays that are sorted by using the Heapsort and Quicksort algorithms, in the worst case, this method is an O(n log n) operation, where n is length.

它还提到 introsort 在 2012 年开始与 .NET 4.5 一起使用。

为什么是List<T>.Sort在最坏的情况下仍然是 O(n^2)？或者这只是文档中的一个错误，实际上是 O(n log n)？

Answer 1

Introsort在最坏的情况下是 O(n log n)。

据我所知，introsort 存在的唯一原因首先是为了避免快速排序的 O(n²) 最坏情况运行时间。

所以说它是 O(n²) 的链接是错误的。

请注意，这两个链接给出了完全相同的算法，逐字逐句(减去似乎是打字错误 - Log^N 而不是 log N)。

• If the partition size is fewer than 16 elements, it uses an insertion sort algorithm

• If the number of partitions exceeds 2 log n, where n is the range of the input array, it uses a Heapsort algorithm.

• Otherwise, it uses a Quicksort algorithm.

然而，他们最终得出了不同的最坏情况的复杂性。

in the worst case, this method is an O(n log n) operation

对比

in the worst case it is an O(n²) operation