What is the time complexity of Linq OrderBy().Then

问题:

I am using Linq and Lambda Operations in my projects and I needed to sort a List according to two properties of a class. Therefore, I used OrderBy().ThenBy() methods as below:

class ValueWithIndex{
    public long Value;
    public int Index;
}
...

List<ValueWithIndex> valuesWithIndex = new List<ValueWithIndex>();

for (int i = 0; i < A.Length; i++){
    ValueWithIndex vi = new ValueWithIndex();
    vi.Value = A[i];
    vi.Index = i;
    valuesWithIndex.Add(vi);
}
var orderedValues = valuesWithIndex.OrderBy(v => v.Value).ThenBy(v => v.Index);

...

In This answer, it is explained that, OrderBy() uses Quicksort, so even if it has O(N*logN) average time complexity, for the worst case, time complexity is around O(N²). If also ThenBy() method has a worst time complexity of O(N²), it would be pointless to use these methods.

Is ThenBy() method use Quicksort, too? If yes, does it mean that for the same "v.Value"s, "v.Index"es are sorted with O(N²) worst time complexity?

回答1:

The LINQ OrderBy(...).ThenBy(...)...ThenBy(...) method chain form a single sort operation by multiple sort keys (using multi key comparer).

Thus, regardless of how many ThenBy(Descending) methods do you include in the chain, the time complexity of the sort operation stays the typical for QuickSort O(N*logN) average / O(N²) worst case. Of course more keys you add, comparing two objects will take more time, but the complexity of the sort operation would not change.