平成26年度 秋期 応用情報技術者試験 午前 問6

図では，まず要素1個ずつに分割された状態から，2個ずつの整列済みの列（1 6 / 3 7 / 4 8 / 2 5）にまとめ，次に4個ずつの整列済みの列（1 3 6 7 / 2 4 5 8）にまとめ，最後に全体を1列にまとめています。整列済みの列を2つずつ併合（マージ）していく動きです。

• ア: クイックソート
  誤り。クイックソートは基準値（ピボット）より小さいものと大きいものに分けていく方法で，図のように隣り合う整列済みの列を併合していく動きにはなりません。

• イ: シェルソート
  誤り。シェルソートは一定間隔ごとに取り出した要素どうしを整列し，間隔を狭めていく方法で，データ列を区切って併合する動きにはなりません。

• ウ: ヒープソート
  誤り。ヒープソートはヒープ（2分木）を構成して最大値（最小値）を順に取り出す方法で，図のような動きにはなりません。

• エ: マージソート
  正しい。整列済みの列を2つずつ併合して長い整列済みの列を作っていく，マージソートの動きと一致します。

答え

エ: マージソート