マージソートの特徴として適切なものはどれか。

📝 解説

マージソートは分割統治法を用いた整列アルゴリズムで、「リストを半分ずつに分割し続け、1要素になったらそれ自体が整列済みとみなし、逆順に2つの整列済みリストを合流（マージ）させながら整列する」操作を再帰的に行います。川の合流に例えると、大きな川を上流にさかのぼって細かな支流（1要素）まで分け、下流に向かって整列しながら合流させていくイメージです。最大の特長は「最良・平均・最悪すべてのケースでO(n log n)が保証される」安定性で、クイックソートが最悪O(n2)になりうる欠点をカバーします。また「安定ソート（等しいキーを持つ要素の相対順序が変わらない）」であることも重要な特性で、複数条件での整列に適しています。デメリットはマージ処理に元のデータと同サイズの追加メモリが必要な点で、インプレースではありません。Java（TimSort：マージソートベース）やPython（Timsort）の組み込みソートに採用されています。誤答の「常にO(n2)の計算量」はバブルソート等の非効率なアルゴリズム、「インプレースで動作する」はクイックソートや選択ソートの特徴、「小規模データに最も効率的」は挿入ソートの特性です。「マージソート＝常にO(n log n)・安定ソート・追加メモリ必要」と覚えましょう！