Why is my List.Sort method in C# reversing the order of my list?

Question

I have a list of items in a generic list:

• A1 (sort index 1)
• A2 (sort index 2)
• B1 (sort index 3)
• B2 (sort index 3)
• B3 (sort index 3)

The comparator on them takes the form:

this.sortIndex.CompareTo(other.sortIndex)

When I do a List.Sort() on the list of items, I get the following order out:

• A1
• A2
• B3
• B2
• B1

It has obviously worked in the sense that the sort indexes are in the right order, but I really don't want it to be re-ordering the 'B' items.

Is there any tweak I can make to my comparator to fix this?

Answer 1

you need to use a "stable sort" algorithm if you don't want items that are equal to change position.

Check out "merge sort" for an example of a stable sort algorithm. Here's an implementation of it in C#.

Answer 2

You can change your comparator to do a secondary sort on the value:

if (this.sortIndex.CompareTo(other.sortIndex) == 0) // same sortIndex
{
   return this.Value.CompareTo(other.Value);
}
return 0;

Answer 3

OrderBy preserves order for equal items:

myList = myList.OrderBy(item => item.SortIndex).ToList();

Answer 4

Sort uses QuickSort, and it doesn't assure original sequence in case of comparison equality.

If you still want to use List.Sort you could add a second comparison with the original index like:

int c = this.sortIndex.CompareTo(other.sortIndex);
if (c == 0)
  c = this.originalIndex.CompareTo(other.originalIndex);
return c;

otherwise you can sort with other "stable" algorithms (e.g. LINQ OrderBy).