安定＝等しいキーの相対順序を保存。計算量や省メモリとは別概念とは？

安定な整列では、同じキーの要素の順序が入力時のまま保たれる。マージソートや挿入ソートは安定、単純な選択ソートやクイックソートは一般に不安定とされる。 ▍なぜ正解 整列の安定性とは、キー値が等しい要素どうしについて、整列前の相対的な並び順が整列後も保存される性質をいう。複数の項目で段階的に整列する場合などに、先の整列結果を崩さない利点がある。 ▍よくある間違い 安定性を「最速」や「省メモリ」といった別の性質と取り違える。 ▍試験の狙い 安定性は「等しいキーの順序が変わらないか」だけを問う性質と押さえる。