マージソート
まーじそーと
定義
データを半分ずつに分割した後、整列しながらマージする整列アルゴリズム。
詳細解説
分割統治法に基づくアルゴリズムで、配列を半分に分割を繰り返し、最小単位から整列しながら統合（マージ）していく。計算量はO(n log n)で安定ソート。クイックソートより最悪計算量が安定（常にO(n log n)）だが、追加メモリ領域が必要な欠点がある。外部ソート（メモリに収まらない大規模データのソート）に適しており、データベース処理で用いられる。
「マージソート」が出る問題
アルゴリズムの計算量を表すO記法（ビッグオー記法）で、二分探索のアルゴリズムの計算量はどれか。
見る人に意図が伝わりやすいデザインにするための四つの原則に関する次の記述中のa、bに入れる字句の適切な組合せはどれか。 [四つの原則] 近接：互いに関連する要素は近づけてグループにする。 [a]：要素を意図したルールに基づき配置する。 反復：要素ごとにデザインルールを繰り返す。 [b]：要素ごとの大小や強弱などの違いを明確にする。 組合せ: ア a=整列 b=価値 イ a=整列 b=対比 ウ a=操作 b=価値 エ a=操作 b=対比
4個の要素から成るデータの並びを、次の手順を繰り返して昇順に整列するとき、整列が終了するまでに(1)から(3)の一連の手順は、何回実行されるか。ここで、最初はデータの並び全体を整列対象とする。データの並び：[27, 42, 33, 12] 〔手順〕(1)整列対象中の要素の最大の値を選び、最後の要素と入れ替える。(2)最後の要素を整列対象から外す。(3)整列対象に要素が1個以上残っていれば、(1)から(3)の一連の手順を実行する。残っていなければ、整列完了なので終了する。
関連用語
よくある質問
Q. マージソートとは何ですか？
A. データを半分ずつに分割した後、整列しながらマージする整列アルゴリズム。
Q. IT パスポート試験での位置づけは？
A. テクノロジ系の重要用語です。出題頻度は 1/3 （★1）。 出題頻度は低めですが、周辺知識として理解しておきましょう。