29

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(N2). If also ThenBy() method has a worst time complexity of O(N2), 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(N2) worst time complexity?

Community
  • 1
  • 1
tuncay altınpulluk
  • 403
  • 1
  • 4
  • 9
  • 1
    It is `O(1)` because in only construct query, not execute it. Also `ThenBy` does not lead to additional ordering, when query executed, it just modify already queued ordering condition. – user4003407 Dec 18 '16 at 22:27
  • 2
    you cant say its `O(1)` because its differed execution. when you need it that's the time you use it and its `O(nlogn)` – M.kazem Akhgary Dec 18 '16 at 22:48
  • @M.kazemAkhgary I don't think it is a bad answer (to say O(1)) considering that OP has not shown what he does with `orderedValues`. – Phil1970 Dec 18 '16 at 23:03
  • Why would that be important? In the excerpt he swown it is O(nlogn). – skyhunter96 Mar 13 '23 at 05:11

1 Answers1

45

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(N2) 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.

Ivan Stoev
  • 195,425
  • 15
  • 312
  • 343
  • 1
    So what I understand is, `.OrderBy(...).ThenBy(...)` method chain sorts the List only once in a single operation and it increases the time of sort, but time complexity stays same as a single `.OrderBy(...)`. Thank you for the answer. – tuncay altınpulluk Dec 18 '16 at 23:11
  • 6
    You've got it right: ) Actually it doesn't necessarily increase the time of sort, because as usual for the multi key comparers, the second, third etc, comparer is called only if the previous comparers return equal, i.e. depends of how many duplicate keys you have at first, second etc. level. In your example, `Index` will be compared only for items with equal `Value`. – Ivan Stoev Dec 18 '16 at 23:16