テクノロジ系出題頻度 1/3
マージソート
まーじそーと
定義
データを半分ずつに分割した後、整列しながらマージする整列アルゴリズム。
詳細解説
分割統治法に基づくアルゴリズムで、配列を半分に分割を繰り返し、最小単位から整列しながら統合（マージ）していく。計算量はO(n log n)で安定ソート。クイックソートより最悪計算量が安定（常にO(n log n)）だが、追加メモリ領域が必要な欠点がある。外部ソート（メモリに収まらない大規模データのソート）に適しており、データベース処理で用いられる。
「マージソート」が出る問題に挑戦
読んだ内容は“思い出す”ほど記憶に残ります。解答・解説つき・基本無料で確認できます。
アルゴリズムの計算量を表すO記法（ビッグオー記法）で、二分探索のアルゴリズムの計算量はどれか。
4個の要素から成るデータの並びを、次の手順を繰り返して昇順に整列するとき、整列が終了するまでに(1)から(3)の一連の手順は、何回実行されるか。ここで、最初はデータの並び全体を整列対象とする。データの並び：[27, 42, 33, 12] 〔手順〕(1)整列対象中の要素の最大の値を選び、最後の要素と入れ替える。(2)最後の要素を整列対象から外す。(3)整列対象に要素が1個以上残っていれば、(1)から(3)の一連の手順を実行する。残っていなければ、整列完了なので終了する。
アルゴリズムにおける「二分探索法」の説明として、最も適切なものはどれか。
関連用語
よくある質問
Q. マージソートとは何ですか？
A. データを半分ずつに分割した後、整列しながらマージする整列アルゴリズム。
Q. IT パスポート試験での位置づけは？
A. テクノロジ系の重要用語です。出題頻度は 1/3 （★1）。 出題頻度は低めですが、周辺知識として理解しておきましょう。