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

OrderBy preserves order for equal items:

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

Answer 2

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