R6RS:翻訳:Rationale:Sorting

16 章 並べ替え

(rnrs sorting (6)) の手続きでは、多くのプログラムにとって有益な並べ替えアルゴリズムへの簡単なインタフェースを提供する。特に、list-sort や vector-sort は比較手続きの O(n log n) 回の呼び出しによる、安定な並べ替えを保証している。単純なマージソートの実装 [7] はこの性質を満たしている。またさらに、マージソートを使うかぎりには、並べ替えの安定性は何ら、実装上・性能上の問題にならないことも重要である。

比較関係として「厳密に小である」ことを選んだのは、既存の並べ替えライブラリとの最大公約数をとったものである。またさらに、真理値を返す手続きではなく、（より小、より大、等値に）値を 3 種返す比較手続きを使うのは、有意な性能上の利点もなく、並べ替え手続きの呼び出しを不便なものにするであろうと思われる。

vector-sort! の仕様は処理系がクイックソート [17] を利用することを認めている。すなわち、比較手続きの呼び出しの上限を O(n^2) 回とすることを認め、並べ替えの安定性を要求しないことになっている。