JavaScriptで、安定ソートをFeature Detectionできるのか

別な質問に回答する過程で調査していたところ、ES2019では、Array.prototype.sortが「The sort must be stable」となっていました（ECMA）。

とはいえ、そうでない過去のブラウザがある以上、この挙動に頼るには検証が必要となります。

…が、「ソートが安定である」ことをFeature Detectionする方法はありますでしょうか。

特定のパターンの配列で試して、実際に安定性が崩れていれば「安定でない」と結論付けられます。ただ、逆に何回やっても安定な結果が返ってきたとしても、それは「実行したデータ（あるいはその場面）に限ったこと」なのか「ソートが安定だと保証されている」のか区別が付きません。

そのような壁を超えて「安定性を確認する」ような方法がありましたら、ご提示いただれば幸いです。

行動規範の内容に同意します

回答1件

ベストアンサー

少なくとも、通常のブラックボックステストで安定でないソートを確実に検出するのは不可能だと思います。

例えば、引数が 10 未満かどうかを返すだけの非常に単純な関数でさえ、

javascript
1const underTen = n => {
2	if (n === 5) return false;
3	return n < 10;
4}

のように実装されていると、ソースコードを見ない限り引数に 5 を指定したときのバグを検出することは困難です。

同様に、

javascript
1Array.prototype.sort = function() {
2	if (this が特定の値である) {
3		安定でないソートを行う
4	} else {
5		安定ソートを行う
6	}
7}

のように実装されていると、ソースコードを見ない限り安定でないソートを行うコード部分を実行させることは困難です。
特に、ソートでは複数のアルゴリズムを組み合わせて実装することが珍しくなく、データに合わせて条件分岐でアルゴリズムを切り替えていると思われるので、上記のコードほど極端ではないとしても似たコードになっていても不思議はありません。

なので、安定ソートで実装されているかを検証するためには、どうしてもソースコードを見る必要があると思います。

あるソート関数が常に安定ソートを行うかどうかを正しく判定する関数は存在しないことの証明

理論上、あるソート関数が常に安定ソートを行うかどうかを正しく判定する関数は存在しないと思われます。
停止性問題と同じ要領で以下のように証明できると思います。

もしも、あるソート関数が常に安定ソートを行うかどうかを正しく判定する関数 isStable が存在すると仮定する。

javascript
1function isStable(sortFunction) {
2	if (sortFunction が常に安定ソートを行う) {
3		return true
4	} else {
5		return false
6	}
7}

ここで、配列をソートする mySort 関数を以下のように定義する。

javascript
1function mySort(array) {
2	if (isStable(mySort)) {
3		array を安定でないソートする
4	} else {
5		array を安定ソートする
6	}
7}

もしも、mySort が常に安定ソートを行うと仮定する。
その場合、isStable(mySort) は true となる。
isStable(mySort) は true のため、mySort の定義から mySort は安定でないソートを行う。
これは、mySort が常に安定ソートを行うという仮定に矛盾する。

もしも、mySort が安定でないソートを行うと仮定する。
その場合、isStable(mySort) は false となる。
isStable(mySort) は false のため、mySort の定義から mySort は常に安定でないソートを行う。
これは、mySort が安定でないソートを行うという仮定に矛盾する。