Keep the relative order of items of same value when keep sorting a list

Question

Suppose you need to keep a changing list, which may contain items of duplicate values, sorted. For example you had [99, 99, 90, 89], but the 4th item's value has changed to 91. You would want it to be [99, 99, 91, 90], but you would not want the order of the first and the second item to change.

I used the Sort() method but it seems that it may change the order of the first and the second items of the example above. Is there any way to prevent it and keep the relative order of items which have the same values?

In case if you cannot think of why this would be necessary, suppose a progress list. The items in the list are updated every second. When the items are sorted by the progress, you would want the items of the same progress keep changing their relative positions.

I have created a sample code to test this. The goal would be reaching Debug.WriteLine("No change");.

public void Start()
{
    var list = new List<Item>();
    var ran = new Random();
    const int nItems = 30;
    for (int i = 0; i < nItems; i++)
    {
        var name = "Item " + (list.Count + 1);
        var item = new Item(name, ran.Next(0, 10));
        list.Add(item);
    }

    var sorter = new ItemComparer();
    var snapshot = new Item[nItems];
    for (int nSort = 0; nSort < 10000; nSort++)
    {
        list.CopyTo(snapshot);
        list.Sort(sorter);

        if (nSort == 0)
        {
            //Sorted for the first time, so the snapshot is invalid.
            continue;
        }

        for (int pos = 0; pos < nItems; pos++)
        {
            if (snapshot[pos] != list[pos])
            {
                Debug.WriteLine($"Order changed at position {pos} after {nSort} sorts.");
                PrintChangedLocation(list, snapshot, pos);
                return;
            }
        }
    }

    Debug.WriteLine("No change");
}

private static void PrintChangedLocation(List<Item> list, Item[] snapshot, int changedLocation)
{
    Debug.WriteLine($"Before\t\t\tAfter");
    for (int pos = 0; pos < list.Count; pos++)
    {
        var before = snapshot[pos];
        var after = list[pos];
        Debug.Write($"{before.Name} = {before.Progress}");
        Debug.Write($"\t\t{after.Name} = {after.Progress}");

        if (pos == changedLocation)
        {
            Debug.Write(" <----");
        }
        Debug.WriteLine("");
    }
}

class Item
{
    public string Name;
    public float Progress;

    public Item(string name, float progress)
    {
        Name = name;
        Progress = progress;
    }
}

class ItemComparer : IComparer<Item>
{
    int Direction = -1; 

    public int Compare(Item x, Item y)
    {
        return Direction * (int)(x.Progress - y.Progress);
    }      
}

Sample output:

Order changed at position 12 after 1 sorts.
Before          After
Item 7 = 9      Item 7 = 9
Item 24 = 9     Item 24 = 9
Item 30 = 8     Item 30 = 8
Item 4 = 8      Item 4 = 8
Item 19 = 8     Item 19 = 8
Item 27 = 7     Item 27 = 7
Item 5 = 7      Item 5 = 7
Item 25 = 7     Item 25 = 7
Item 20 = 7     Item 20 = 7
Item 26 = 6     Item 26 = 6
Item 14 = 6     Item 14 = 6
Item 1 = 6      Item 1 = 6
Item 28 = 5     Item 2 = 5 <----
Item 2 = 5      Item 12 = 5
Item 12 = 5     Item 28 = 5
Item 11 = 4     Item 11 = 4
Item 6 = 4      Item 6 = 4
Item 13 = 3     Item 13 = 3
Item 3 = 3      Item 3 = 3
Item 21 = 3     Item 21 = 3
Item 10 = 3     Item 10 = 3
Item 18 = 3     Item 18 = 3
Item 22 = 2     Item 22 = 2
Item 29 = 2     Item 29 = 2
Item 23 = 1     Item 23 = 1
Item 8 = 1      Item 8 = 1
Item 17 = 1     Item 17 = 1
Item 16 = 0     Item 9 = 0
Item 9 = 0      Item 16 = 0
Item 15 = 0     Item 15 = 0

Answer 1

One option to consider would be changing:

list.Sort(sorter);

to:

list = list
    .Select((item, index) => new { item, index})
    .OrderBy(z => z.item, sorter)
    .ThenBy(z => z.index)
    .Select(z => z.item)
    .ToList();

This allows you sort by your comparer, then by its position in the List - thus keeping the relative order.