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?
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.