[Mono-dev] Bug 582502 - System.Linq.Enumerable.OrderByDescending is not a stable sort

[dinonet at gmx.de]

> 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.
> 
> Thanks,
> 
> 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.!
http://portal.gmx.net/de/go/dsl02