Swiftのsortが、要素数が増えると安定ではなくなる話

はじめに

タイトル通り。これではまった。

調べたこと

コード

以下のコードで、sortの挙動を調べた。
わかりやすいように、sortの処理はつなげて書かずに分割してある。

typealias Pair = (Int, Int)

// 要素数21個の場合
let array1 = (0 ... 20).map { i in
    Pair(i / 5, i)
}

// tupleの2つめの要素でsortしてから
let sorted1 = array1.sorted { (p1, p2) in
    p1.1 < p2.1
}

// tupleの1つめの要素でsort
let sorted12 = sorted1.sorted { (p1, p2) in
    p1.0 < p2.0
}

print(sorted12)

// 要素数501個の場合も同じことをする
let array2 = (0 ... 500).map { i in
    Pair(i / 5, i)
}

let sorted2 = array2.sorted { (p1, p2) in
    p1.1 < p2.1
}

print(sorted2)

let sorted22 = sorted2.sorted { (p1, p2) in
    p1.0 < p2.0
}

print(sorted22)

結果

要素数21の場合は安定なのに、要素数501の場合は安定ではなくなっている様子がおわかりいただけるだろうか。

原因

未調査。Swiftのコードを読もう。

最後に

安定じゃないと困るようなsortをするときは気をつけよう。私は自前でマージソートを実装して乗り切った。