問題 No.2421
すでに整列された複数のデータリストを分割してそれぞれを個別に整列し、最終的にそれらを順序を崩さないように統合して一つにまとめることで全体を並び替える整列アルゴリズムはどれか。
【正解の解説】
マージソート（統合ソート）
トランプの束を一度バラバラの小さな束に分けてから、それぞれ順番通りに綺麗に並べ、隣同士の束を順番を確認しながら一つに合体させていく作業にそっくりです。大人数のチームで手分けして作業してから、最後にパズルのようにきれいに組み合わせる効率の良い方法です。
スポンサーリンク
【その他の選択肢の解説】
クイックソート（分割統治法）
マージソートが「細かく分けてから最後に合体させる」のに対し、クイックソートは「基準を決めてスパッとグループ分けを繰り返す」点が大きく異なります。名前や言葉の響きが似ているため試験で混同しやすいですが、データの動かし方が根本的に違うので注意しましょう。
バブルソート（交換法）
水中の泡がボコボコと地上に向かって浮き上がっていくように、一番大きな値が端っこへ移動していく様子からこの名前がついています。データを分割・統合するマージソートとは違い、地道に隣同士を比べるため、データ数が多いと非常に時間がかかるという特徴があります。
ヒープソート（選択法）
データのまとまりの中から常に一番強い（大きい）ものを王様として選び出し、それを端に追いやる作業を繰り返します。データを細かく分割して合体させるマージソートとは仕組みが異なり、メモリを効率よく使って高速に並び替えたい時によく使われる別のアプローチです。