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

This topic is 3039 days old which is more than the 365 day threshold we allow for new replies. Please post a new topic.

## Recommended Posts

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 on other sites
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, key) > 0)            {                list[i + 1] = list;                i--;            }            list[i + 1] = key;        }    }}

In use:
mGameObjects.InsertionSort(CompareByRenderPriority);

Thanks, Mike.

##### Share on other sites
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 on other sites
You might also consider using the LINQ OrderBy method. MSDN says that it is stable sort.

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

• 18
• 11
• 16
• 9
• 50
• ### Forum Statistics

• Total Topics
631396
• Total Posts
2999783
×