.NET List<T>.Sort uses introsort, why is the worst case O(n^2)?

user_10332586 0
Viewed 747

The .NET documentation of List<T>.Sort mentions the asymptotic runtime: https://docs.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.

It also mentions that it's implemented using Array.Sort, which also has a runtime claim at: https://docs.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.

It also mentions that introsort started being used with .NET 4.5, in 2012.

Why is List<T>.Sort still O(n^2) in the worst case? Or is that just a mistake in the documentation and it's in fact O(n log n)?

sorting algorithm .net c#
2 Answers

Introsort is O(n log n) in the worst case.

As far as I know, the only reason introsort exists in the first place is to avoid the O(n2) worst-case running time of quicksort.

So the link saying it's O(n2) is wrong.

Note that the two links give exactly the same algorithm, word-for-word (minus what appears to be a typing error - LogN instead of 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.

Yet they end by concluding different worst-case complexities.

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

versus

in the worst case it is an O(n2) operation

user_17117960

I think it might be an approximation issue. Take your second quote:

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.

I've seen tons of textbooks/articles describing quicksort as being O(n log n), while in fact you can double check here and verify its worst case cost is actually O(n²). That's usually because in practice, quicksort is almost always faster than other sorting algorithms that on paper have a smaller worst case cost. For instance, you'll see that the block sort has O(n log n) as worst case, but still the quicksort will be faster in the majority of practical applications.

As for your first quote: I'd say that's because the docs mention the worst cose among the possible cases. Specifically:

  • If the partition size is smaller than 16, it goes with insertion sort, which is O(n²) (though it can be seen as O(1) here as it's bounded to 16).
  • If the partition […] it goes with heapsort, which is O(n log n).
  • Otherwise it goes with quicksort, which is in fact O(n²).

So I'd say that could be why the List<T>.Sort method as being described as O(n log n) on average, and O(n²) in the worst case here.

user_38139760
Related