How to force stable sort for ArrayList with a custom IComparer?

Question

According to the docs:

To perform a stable sort, you must implement a custom IComparer interface.

But according to this post.

What the documentation appears to be saying is that the only way you can get a stable sort with ArrayList.Sort is to use an IComparer that somehow 'knows' the indices of the items that are being compared (one would imagine accomplishing this by making it run an initial pass on the collection) and uses that information as a tie-breaker for otherwise equal elements.

So does anyone know how to properly implement an IComparer that somehow 'knows' the indices of the items that are being compared?

Answer 1

You could build something like this (borrowing code from this answer by Jon Skeet)

public sealed class IdentityEqualityComparer<T> : IEqualityComparer<T>
    where T : class
{
    public int GetHashCode(T value) => RuntimeHelpers.GetHashCode(value);

    public bool Equals(T left, T right) => left == right;
}

public class StableComparer : IComparer
{
    private readonly Dictionary<object, int> _itemsPosition = 
        new Dictionary<object, int>(new IdentityEqualityComparer<object>());

    private readonly IComparer _baseComparer;

    public StableComparer(IEnumerable collection, IComparer baseComparer)
    {
        _baseComparer = baseComparer;

        int index = 0;
        foreach (object item in collection)
        {
            _itemsPosition.Add(item, index);
            index++;
        }
    }

    public int Compare(object x, object y)
    {
        int baseResult = _baseComparer.Compare(x, y);
        if (baseResult != 0)
        {
            return baseResult;
        }

        int xIndex = _itemsPosition[x];
        int yIndex = _itemsPosition[y];

        return xIndex.CompareTo(yIndex);
    }
}

(I added the equality comparer part to make sure reference equality is used as suggested by @PeterDuniho).

This code can be used like this:

class Item
{
    public int Id { get; }
    public string Description { get; }

    public Item(int id, string description)
    {
        Id = id;
        Description = description;
    }
}

class ItemComparer : IComparer
{
    public int Compare(object x, object y) => ((Item)x).Id.CompareTo(((Item)y).Id);
}

and

class Program
{
    static void Main(string[] args)
    {
        var items = new ArrayList()
        {
            new Item(1, "Item 0 (1)"),
            new Item(3, "Item 1 (3)"),
            new Item(2, "Item 2 (2)"),
            new Item(3, "Item 3 (3)"),
            new Item(1, "Item 4 (1)"),
            new Item(4, "Item 5 (4)"),
            new Item(1, "Item 6 (1)")
        };

        Console.WriteLine("Not stable");
        SortAndDisplay((ArrayList)items.Clone(), new ItemComparer());

        Console.WriteLine("Stable");
        SortAndDisplay((ArrayList)items.Clone(), 
          new StableComparer(items, new ItemComparer()));
    }

    static void SortAndDisplay(ArrayList items, IComparer comparer)
    {
        items.Sort(comparer);

        foreach (var item in items)
        {
            Console.WriteLine(((Item)item).Description);
        }
    }
}

Note that there were changes on Sort in framework 4.5 which can change the ordering of 'equal' items. If I run this code in Framework 4, I get:

Not stable
Item 6 (1)
Item 4 (1)
Item 0 (1)
Item 2 (2)
Item 3 (3)
Item 1 (3)
Item 5 (4)
Stable
Item 0 (1)
Item 4 (1)
Item 6 (1)
Item 2 (2)
Item 1 (3)
Item 3 (3)
Item 5 (4)

I tried to post this code to .net Fiddle but it does not allow using framework 4. You could use Linq's OrderBy too which is stable.