Stable Sort

.Net does not use a stable sort for its List<t> Sort method. Watch out!

A stable sort is a sort that preserves the original order for items that are considered equal.

For example, take the following list of objects:

Name, Group
John, Group 3
Sally, Group 2
Bill, Group 2
Joe, Group 3
Alf, Group 1

Now, sort these objects on the 'Group':

Alf, Group 1
Sally, Group 2
Bill, Group 2
Joe, Group 3
John, Group 3

You'll notice that the list is correctly sorted by group and the names are ignored. That is as it should be. You will also notice that Joe appears before John where in the previous list he did not. That is going to cause problems and here is why. Resort the sorted list on Group again:

Alf, Group 1
Bill, Group 2
Sally, Group 2
John, Group 3
Joe, Group 3

You'll notice that the list is correctly sorted by group but that the names have shuffled around. If you resort a third time you'll get back to the 1st sorted list. Logically you'd expect an already sorted list not to be changed by a sort algorithm. That kind of sort is called a stable sort and .Net doesn't use one. It's not a bug and it's not wrong but it may not be what you expected.

The solution is to use a stable sort algorithm by rolling your own or by sorting on unique keys. For our example we'd sort on Group then Name in order to get a determinate sort order from the unstable sort algorithm.