What Sorting Algorithm Is Used By LINQ "OrderBy"?

Question

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:

• Jon Skeet on OrderBy stability
• Troy Magennis on OrderBy stability

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 1

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.