Document Sorting as Stable

stable sort とは、比較結果が等しい（または順序付けできない）要素同士の相対順序を、ソート前と同じまま保つソートのことです。たとえば姓でソート済みのプレイヤー一覧を、今度は名でソートしても、同じ名のプレイヤーは元の姓の順序のまま残ります。

var roster = [
   Player(first: "Sam", last: "Coffey"),
   Player(first: "Ashley", last: "Hatch"),
   Player(first: "Kristie", last: "Mewis"),
   Player(first: "Ashley", last: "Sanchez"),
   Player(first: "Sophia", last: "Smith"),
]

roster.sort(by: { $0.first < $1.first })
// roster == [
//    Player(first: "Ashley", last: "Hatch"),
//    Player(first: "Ashley", last: "Sanchez"),
//    Player(first: "Kristie", last: "Mewis"),
//    Player(first: "Sam", last: "Coffey"),
//    Player(first: "Sophia", last: "Smith"),
// ]

整数の配列のように Comparable 適合だけでソートする場合、等しい要素は見分けが付かないので stability は観察できません。しかし、要素のプロパティの一部だけを使ってソートする場合には、stability の有無が結果に表れます。スプレッドシートで複数の列を順にソートして多段ソートを実現するような使い方は、stability を前提としています。

標準ライブラリの sort() は Swift 5 より前のタイミングで stable な実装に変更されていました。しかし、ドキュメント上は次のように「stable とは保証しない」と明記されたままでした。

The sorting algorithm is not guaranteed to be stable. A stable sort preserves the relative order of elements that compare as equal.

この状態は、stability を知っている開発者にとっては「実際には stable なのに頼ってよいか分からない」という不便さにつながり、stability を知らない開発者にとっては「将来 stable でなくなったら原因不明のバグを踏みかねない」というリスクにつながっていました。