What is time complexity of LINQ Order()/OrderBy() followed by Take(k)?

Question

What is the time complexity of the following code in C#?

array.Order().Take(k).ToArray();

Will LINQ treat this as QuickSelect? Or, will it perform full array sorting with the complexity O(n log n)?

Answer 1

This behaviour is not guaranteed by the documentation. However, the current implementation uses a partial QuickSort for .OrderBy().Skip/Take, and a QuickSelect for .OrderBy().First/Last/ElementAt.

This means that the time complexity for .OrderBy().Take(k) is O(n + k log k) Average and O(n²) Worst.

This was implemented in this pull request, back in 2016 (meaning that this was in .NET Core 1.0). This was a deliberate optimisation which was added some time ago, meaning that there is very little chance of it being removed, in practice.