テクノロジ
マージソートとは
読み方：マージソート
ひとことで言うと：列を分割してそれぞれ整列し、整列済み列を併合する分割統治型の整列法。
意味をわかりやすく解説
マージソートは、データ列を半分ずつ分割し、小さな列を整列してから、二つの整列済み列を順序を保って併合する分割統治型の整列法です。
時間計算量は最悪でもO(n log n)で安定しています。通常は併合用に追加の記憶領域が必要ですが、安定ソートとして実装できます。
具体例
[1,4]と[2,3]を併合するとき、両列の先頭を比較し、小さい1→2→3→4の順に新しい列へ入れます。
似た用語との違い
覚え方
半分に割る→それぞれ整列→マージする。
基本情報技術者試験の試験ポイント
計算量O(n log n)、安定性、追加領域、併合手順を比較問題で押さえます。
CHECK QUESTION
マージソートの最悪時間計算量は一般に何ですか。
答えを見る
O(n log n)です。
この説明は分かりやすかったですか？
基本情報技術者試験を勉強中ですか？
この用語を含む重要用語を、単語帳や4択テストで学習できます。