.NET4.5と.NET4のソートは結果が異なる

List.Sort()メソッドを利用する以下のコードは、.NET Framework4.5とそれ以前のバージョンでは異なる結果を返します。

Program.cs

    static class Program
    {
        [STAThread]
        static void Main()
        {
            List<Pair> l = new List<Pair>();

            Random rnd = new Random(0);  // seedを0で固定
            for (int i = 0; i < 100; i++)
            {
                l.Add(new Pair(i, rnd.Next(10)));
            }
            l.Sort(Comparison);

            foreach(Pair p in l)
            {
                Debug.Print("value=" + p.value + ", index=" + p.index);
            }
        }

        static int Comparison(Pair p1, Pair p2)
        {
            return p1.value - p2.value;
        }

    }

    class Pair
    {
        public int index;
        public int value;
        public Pair(int index, int value)
        {
            this.index = index;
            this.value = value;
        }
    }

.NET Framework4.5での結果。

value=0, index=99
value=0, index=36
value=0, index=15
value=0, index=29
value=0, index=64
value=0, index=23
value=1, index=75
value=1, index=66
value=1, index=80
value=1, index=54
value=1, index=98
value=1, index=48
value=1, index=42
value=1, index=30
value=1, index=78
（以下略)

.NET Framework4/3.5での結果。

value=0, index=23
value=0, index=64
value=0, index=15
value=0, index=29
value=0, index=36
value=0, index=99
value=1, index=54
value=1, index=30
value=1, index=48
value=1, index=42
value=1, index=98
value=1, index=78
value=1, index=75
value=1, index=80
value=1, index=66
（以下略)

どうやら、.NET4.5になって、ソートのアルゴリズムに変更があったようです。value値が等しい要素の順序が異なっています。

元のリストにおける要素のインデックスが得られるような好運な状況ならば、Comparison関数を以下のように書けば安定ソートになり、.NETのバージョンによらず常に一定の結果を返します。

Program.cs

        static int Comparison(Pair p1, Pair p2)
        {
            int t = p1.value - p2.value;
            if (t != 0)
            {
                return t;
            }
            else
            {
                // value値が等しいならば、
                // index値(元の配列におけるインデックス)に基づいてソート
                return p1.index - p2.index;
            }
        }

実行結果
value=0, index=15
value=0, index=23
value=0, index=29
value=0, index=36
value=0, index=64
value=0, index=99
value=1, index=30
value=1, index=42
value=1, index=48
value=1, index=54
value=1, index=66
value=1, index=75
value=1, index=78
value=1, index=80
value=1, index=98
(以下略)