What Sorting Algorithm Is Used By LINQ "OrderBy"?

linq algorithm sorting quicksort
Brent Arias picture Brent Arias · May 8, 2010 · Viewed 14.8k times · Source

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?

Answer

Jb Evain picture Jb Evain · May 8, 2010

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.

Related questions

C# Determine Duplicate in List

Requirement: In an unsorted List, determine if a duplicate exists. The typical way I would do this is an n-squared nested loop. I'm wondering how others solve this. Is there an elegant, high performance method in Linq? Something generic that …

Read More
Replacing nested foreach with LINQ; modify and update a property deep within

Consider the requirement to change a data member on one or more properties of an object that is 5 or 6 levels deep. There are sub-collections that need to be iterated through to get to the property that needs inspection & modification. …

Read More
What guarantees are there on the run-time complexity (Big-O) of LINQ methods?

I've recently started using LINQ quite a bit, and I haven't really seen any mention of run-time complexity for any of the LINQ methods. Obviously, there are many factors at play here, so let's restrict the discussion to the plain …

Read More