On page 64 of "LINQ To Objects Using C# 4.0" (Tony Magennis) he states that LINQ's quicksort ordering algorithm is unstable...
...although this is simply solved by cascading the result into a ThenBy or ThenByDescending operator.
Huh? Why would cascading an unstable sortation into another sortation fix the result? In fact, I'd say that isn't possible. The original order, once passed through an unstable sort, is simply lost. What am I missing here?
He's saying if do, say orderby LastName only then anybody with the same last name will be sorted in an unpredictable order. So if you combine it with, say orderby LastName, FirstName you can make the order predictable again (except for people with the same first and last name of course).
At least, that's what I would assume.
Unstable sort means that a chain of x.OrderBy(...).OrderBy(...) calls will only reliably sort according to the final criterion. x.OrderBy(...).ThenBy(...) explicitly captures knowledge of the previous sort order when applying the new sort order. I believe it does this by calling IOrderedEnumerable<TElement>.CreateOrderedEnumerable<TKey>, though I'm not 100% sure of this.
EDIT: Just to be clear, when I say, "captures the knowledge..." I don't mean to suggest that the first OrderBy performs a sort, and somehow the second one knows what it did. Remember that OrderBy returns an IOrderedEnumerable<T>, which doesn't perform any work at all until someone tries to consume the elements. In this scenario, it will never perform the sort, since ThenBy, using knowledge of how OrderBy would have sorted, constructs a brand new sorter that applies both sort orderings in the expected manner and in a single step.
It has been pointed out that Magennis is wrong on the unstable sort thing. The above description is still valid, however.
Put simply, he's wrong. The Linq OrderBy et al. methods are documented as performing a stable sort:
This method performs a stable sort; that is, if the keys of two elements are equal, the order of the elements is preserved. In contrast, an unstable sort does not preserve the order of elements that have the same key.