dotnet / dotnet/dotnet-api-docs

List sort has quadratic worst-case runtime?

Open
#1,109 0 comments 0 reactions 0 assignees View on GitHub
area-System.Collections dotnet-api/prod Pri2 untriaged
Dominant language
C#
Stars
949
Forks
1.7k
Avg merge
3d 27m
Merged PRs (30d)
49

Description

`List.Sort` claims to use `Array.Sort`, which uses introsort. It also claims that the worst-case runtime is `O(n^2)`.

`Array.Sort` claims to use introsort, and it claims that the worst-case runtime is `O(n log n)`. It also claims that this is only the case after .NET 4.5, and it had a `O(n^2)` worst-case in .NET 4.0.

I suspect the `List.Sort` documentation didn't get updated for .NET 4.5?

---
#### Document Details

⚠ *Do not edit this section. It is required for docs.microsoft.com ➟ GitHub issue linking.*

* ID: 36bdb60d-fa8f-84c1-6d7d-e17b06096112
* Version Independent ID: 1dc86b79-6cc3-b1ed-dd07-99559381a82c
* Content: [List<T>.Sort Method (System.Collections.Generic)](https://docs.microsoft.com/en-us/dotnet/api/system.collections.generic.list-1.sort?view=netframework-4.7.2)
* Content Source: [xml/System.Collections.Generic/List`1.xml](https://github.com/dotnet/dotnet-api-docs/blob/master/xml/System.Collections.Generic/List`1.xml)
* Product: **dotnet-api**
* GitHub Login: @dotnet-bot
* Microsoft Alias: **dotnetcontent**

Contributor guide

Open the contributing guide

Assessment

This issue has not been assessed yet.

Get new issues in your inbox

A short digest of beginner-friendly GitHub issues.