[Mono-dev] Bug 582502 - System.Linq.Enumerable.OrderByDescending is not a stable sort
dinonet at gmx.de
dinonet at gmx.de
Wed Mar 24 11:36:03 EDT 2010
> It would appear that the Compare method in SortSequenceContext.cs (lines 58 - 70 revision 152310) does not allow for equality.
> If a comparison returns zero on line 60 and a non-zero child context comparison is never found then Compare will return first_index - second_index on line 66 (which is always going to give you a non-zero number unless you do something silly like compare an index to its self).
> I've fixed this by replacing line 66 to simply return zero in the equality case.
By returning zero you make the sort unstable. If elements are equal they are compared by their original index, which effectively makes any unstable sort stable. It's a very nice trick but only usable if you have the original indices of the elements, which is the case here.
> Unfortunately this breaks the QuickSort.cs implementation. That said, QuickSort by definition is not a stable sort (there are variants which are, but it does not appear that the current implementation is a stable variant).
It obviously breaks because you broke the comparer, which was part of what made it a stable sort :)
> To solve this; I replaced QuickSort with MergeSort and everything works as it is supposed to. I'm not sure if the desired solution is to use MergeSort or a stable QuickSort, but if you'd like a MergeSort implementation I would be happy to supply it.
> Richard Kiene
What the original bug report observed was not an unstable sort, but a stable sort which reversed the order of "equal" elements. I guess somewhere in the "Descending" variant it reverses the orignal list before doing the stable sort. But I need to check the sources again.
GMX DSL: Internet, Telefon und Entertainment für nur 19,99 EUR/mtl.!
More information about the Mono-devel-list