安定なソートください
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; } }