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

[Richard Kiene]

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.

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

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