C# のソートでハマった話

C#(mono 2.10.9) で、特定の値を先頭に持ってきつつソート、というのをしようとした。
こんな感じかなー。

var list = new List<int>{1, 2, 3, 4, 5, 6, 7, 8, 9, 10};
int t = 5;  // 5 を先頭に持って行きたい
list.Sort((a, b) => {
    if (a == t) return -1;
    if (b == t) return 1;
    return a.CompareTo(b);
});
Console.WriteLine(string.Join(", ", list));

1, 5, 2, 3, 4, 6, 7, 8, 9, 10

…え? どういうことなの…。
最初は私の浅はかなアルゴリズムが間違っているのかと思い、かなり確認したがわからず。
試しに比較関数がどう呼ばれているかチェックしてみた。

var list = new List<int>{1, 2, 3, 4, 5, 6, 7, 8, 9, 10};
int t = 5;
list.Sort((a, b) => {
    Console.WriteLine(string.Format("({0}, {1})", a, b));
    if (a == t) return -1;
    if (b == t) return 1;
    return a.CompareTo(b);
});
Console.WriteLine(string.Join(", ", list));

(1, 5)
(5, 10)
(5, 9)
(5, 8)
(5, 7)
(5, 6)
(5, 5)
(5, 4)
(5, 3)
(5, 2)
(2, 5)
(2, 6)
(3, 6)
(4, 6)
(5, 6)
(6, 6)
(6, 10)
(6, 9)
(6, 8)
(6, 7)
(6, 6)
(7, 6)
(6, 5)
(2, 3)
(3, 3)
(3, 5)
(4, 3)
(3, 4)
(3, 5)
(2, 2)
(2, 5)
(4, 4)
(4, 3)
(7, 8)
(8, 8)
(8, 10)
(8, 9)
(8, 8)
(9, 8)
(9, 9)
(9, 10)
1, 5, 2, 3, 4, 6, 7, 8, 9, 10

ふむふむ。…ん!?

(5, 5)

!?
これ比較関数だよね…。なんで同じ値渡してるの…。
もしかして…

var list = new List<int>{1, 2, 3, 4, 5, 6, 7, 8, 9, 10};
int t = 5;
list.Sort((a, b) => {
    if (a == b) return 0;  // 同じ値は当然 0 を返す
    if (a == t) return -1;
    if (b == t) return 1;
    return a.CompareTo(b);
    });
Console.WriteLine(string.Join(", ", list));

5, 1, 2, 3, 4, 6, 7, 8, 9, 10

動いたー！
なんで同じ値が渡ってくる可能性を考慮しないといけないのか。
ていうかさ。

これバグじゃね?

そう思って Visual C# 2012 で確認したところ…

(2, 1)
(3, 2)
(4, 3)
(5, 4)
(5, 3)
(5, 2)
(5, 1)
(6, 4)
(7, 6)
(8, 7)
(9, 8)
(10, 9)
5, 1, 2, 3, 4, 6, 7, 8, 9, 10

まったく問題なし。しかも比較関数呼ばれてる回数圧倒的に少ないですね。
と言うわけで、mono のバグっぽい。最新ベータで直っているかどうかは未確認。