# [.net] [C#] List.Sort is Non-Deterministic?

## Recommended Posts

matthughson    588
Hi, I am trying to use a custom sort delegate with my List in C#. It seems that the result is not deterministic, in that I have a list of items, all with equal values, but the order of the list is different every time I call the Sort method. I call the sort function like so:
mGameObjects.Sort(CompareByRenderPriority);
Here is my implementation of the sort:
// Used to sort the game objects based on render priority.  We want the higher
// priority (which is a smaller number) to appear later on the list.
//
private static int CompareByRenderPriority(GameObject x, GameObject y)
{
// For testing I just return 0 every time, indicating that the
// 2 items are equal.
return 0;
}
Is there a way to tell the list not to change the order of items have the same value? Thanks!

#### Share this post

##### Share on other sites
Mike.Popoloski    3258
From the documentation:

Quote:
 This method uses Array.Sort, which uses the QuickSort algorithm. This implementation performs an unstable sort; that is, if two elements are equal, their order might not be preserved. In contrast, a stable sort preserves the order of elements that are equal.

It's easy enough to whip up your own sorting method though. It's a well-researched field:

static class ListExtensions
{
public static void InsertionSort<T>(this IList<T> list, Comparison<T> comparison)
{
if (list == null)
throw new ArgumentNullException("list");
if (comparison == null)
throw new ArgumentNullException("comparison");

for (int j = 1; j < list.Count; j++)
{
T key = list[j];
int i = j - 1;

while (i >= 0 && comparison(list[i], key) > 0)
{
list[i + 1] = list[i];
i--;
}

list[i + 1] = key;
}
}
}

In use:
mGameObjects.InsertionSort(CompareByRenderPriority);

#### Share this post

##### Share on other sites
matthughson    588
Thanks, Mike.

#### Share this post

##### Share on other sites
AEtheReal    100
If you do not mind making the structure a bit bigger, the solution is easy.

Store the original index of each element. In the compare function, in case of a tie, compare the original index.

#### Share this post

##### Share on other sites
turnpast    1011
You might also consider using the LINQ OrderBy method. MSDN says that it is stable sort.

#### Share this post

##### Share on other sites
Promit    13246
For a stable alternative to Quick Sort, what you really want is Merge sort. In fact, merge sort has a bunch of neat properties.

## Create an account or sign in to comment

You need to be a member in order to leave a comment

## Create an account

Sign up for a new account in our community. It's easy!

Register a new account

## Sign in

Already have an account? Sign in here.

Sign In Now