70

Evidently LINQ's "OrderBy" had originally been specified as unstable, but by the time of Orca it was specified as stable. Not all documentation has been updated accordingly - consider these links:

But if LINQ's OrderBy is now "stable," then it means it is not using a quicksort (which is inherently unstable) even though some documentation (e.g. Troy's book) says it is. So my question is: if not quicksort, then what is the actual algorithm LINQ's orderBy is using?

Improve this question
3
  • 2
    Stictly, Linq's OrderBy is not specified for stability. Enumerable.OrderBy is specified as stable, other providers are free to also offer that promise but may not. Doing so may be impossible or very expensive (consider the impact it would have on parallelisation in terms of p-linq for example) or relatively cheap, which is a big influence on what providers will do. Commented Dec 10, 2016 at 2:21
  • A very related post here. Commented Aug 10, 2017 at 1:43
  • 2
    would it be bad to tag this [c#]? or at least [.net]? I missed this question because I begin all my queries with [c#] (unless I happen to be doing javascript that day)... Commented Dec 12, 2018 at 23:32

4 Answers 4

Reset to default
73

For LINQ to Objects, it's a stable quicksort that is used. For any other kind of LINQ, it's left to the underlying implementation.

Improve this answer
Sign up to request clarification or add additional context in comments.

4 Comments

If I have an object referenced as only IEnumerable<Foo> how does Linq know if it's Linq-to-Objects or something else?
IEnumerable is always Linq to objects (vs IQueryable which is Linq to whatever else)
@Dai IEnumerable<T> is an interface, so it actually depends of what type has the underlying collection (I dont agree with @John). For instance, List<T> implements IEnumerable<T>, and you could have a List<T> declared as IEnumerable<T>. If you perform an order by on this list, the Linq-to-objects provider is used. On the other hand. DbSet<T> also implements IEnumerable<T>. If you perform an order by on this DbSet, even if it is declared as an IEnumerable, Linq-to-sql provider will be used. If you wanted to use linq-to-objects on a dbset, you could do dbset.AsEnumerable().OrderBy(lambda)
@DanielGarcíaRubio DbSet does not directly implement IEnumerable, it implements IQueryable, which in turn always implements IEnumerable. So i dont completely understand why you do not agree with John, as what he said is correct.
43

Boot up reflector, open to System.Linq.EnumerableSorter reveals that Linq2Objects uses the quick sort

Improve this answer

3 Comments

+1 for looking it up. But a simple test shows no n^2 growth in time consumption as elements number of reverse sorted List of int increases, as it should be according to en.wikipedia.org/wiki/Quicksort I tried 1k and 1M elements worst-case - time consumption increased only about 50 times
@EvAlex Quicksort doesn't run in quadratic time. Well, it can, but that's the upper bound and rare. If it were theta(n**2) everyone would just use mergesort.
Now .NET core is opened to everyone :) Why don't you have a closer look? referencesource.microsoft.com/#System.Core/System/Linq/…
18

Quicksort is used, but the reason why it is stable is because the indices of each pair of elements are compared if all the keys test equal.

In other words, you can make any quicksort stable by including in the comparator function a comparison of the original indices of the two elements as a fallback.

Source: http://referencesource.microsoft.com/#System.Core/System/Linq/Enumerable.cs,1395017e067e5a34

Improve this answer

2 Comments

Have been looking for a while for the open source link, thanks
In theory, you could stabilise any sorting algorithm by including the original indices in the comparator. The challenge is figuring out the best data structure to use to keep track of these original indices.
3

I am under the understanding that OrderBy gets translated into SQL that performs the sort on the Database. At least in the case of LINQ to SQL

Improve this answer

1 Comment

Yes, but that's only true for Linq to SQL and other database Linq providers. Linq is not just an ORM... (Linq to Objects, Linq to XML...)

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.