安定ソートとは
ソート（並び替え）を実行した際に、順序が等しいものとして扱われる要素の順序が変化しないことが保証されているアルゴリズムを安定ソートと言います。
例えば以下のようなオブジェクトの配列があり、age プロパティでソートする場合に Alice と Charlie の順序が入れ替わらないことが保証されます（昇順、降順問わず必ず Alice の次に Charlie が来る）。
const users = [
{ name: "Alice", age: 30 },
{ name: "Bob", age: 25 },
{ name: "Charlie", age: 30 },
];
有名なアルゴリズムだと挿入ソートやマージソートは安定ソートですが、クイックソートは不安定ソートです。
仕様におけるソート安定化の動き
ECMAScript で定義されている Array.prototype.sort と %TypedArray%.prototype.sort はかつて安定性について特に定められておらず、実際に V8 などのいくつかのメジャーな JavaScript エンジンで不安定ソートとなっていました。
自分も過去にこの問題を解決するために、ES Discuss というメーリングリスト[1]で提案したことがあります。
転機が訪れたのは2018年9月のこと。V8 が安定ソートに切り替えたのに呼応して、今まで不安定ソートだったメジャーなエンジンの実装が全て安定ソートに切り替わりました。そして仕様側で sort メソッドの安定を必須化しようと議論され、承認されました。
ES2023 Change Array by Copy の考慮漏れ対応
ES2023 に入った Change Array by Copy の提案によって Array.prototype.toSorted と %TypedArray%.prototype.toSorted が追加されました。sort メソッドが配列を破壊的に変更するのに対し、toSorted メソッドは配列をコピーしてから並び替える非破壊的なものとなっています。
るまさんによりこれら toSorted メソッドの安定必須化を明記し忘れられていたことが発見され、報告されました。その後2024年10月の会議で承認され、安定ソートであることが明記されました。
Discussion