整列アルゴリズムが「安定である」とは、どういう意味か。

解説

正解は「同じキーをもつ要素の相対的な順序が、整列の前後で変わらない」です。例えば、学生のデータを学籍番号順に並べた後、点数で安定なソートを行うと、同じ点数の学生は学籍番号順のまま並びます。複数のキーで段階的に整列するときに重要な性質です。マージソート、挿入ソート、バブルソートは安定に実装でき、クイックソート、ヒープソート、選択ソートは一般に安定ではありません。「入力によらず、実行時間が一定である」は計算量に関する性質で、安定性とは別のものです。「追加の作業領域を使わずに整列できる」は in-place と呼ばれる性質です。「整列済みのデータを入力しても、計算量が悪化しない」も安定性の定義ではありません。