安定なソートください

C#(.NET Framework) で地味に困ることのひとつが、標準のコレクションフレームワークのソートがJavaと違って安定でないこと。マージソートくらい自分で実装してみせろ!というMicrosoftの愛のムチを無視して、逃げに走る。

static void StableSort<T>(List<T> list, Comparison<T> comparison)
{
    List<KeyValuePair<Int32, T>> wrapped = new List<KeyValuePair<Int32, T>>(list.Count);
    for (Int32 i=0; i<list.Count; i++)
    {
        wrapped.Add(new KeyValuePair<Int32, T>(i, list[i]));
    }

    wrapped.Sort(delegate(KeyValuePair<Int32, T> x, KeyValuePair<Int32, T> y)
    {
        Int32 result = comparison(x.Value, y.Value);
        if (result == 0)
        {
            result = x.Key.CompareTo(y.Key);
        }
        return result;
    });

    for (Int32 i = 0; i < list.Count; i++)
    {
        list[i] = wrapped[i].Value;
    }
}