情報処理技術者試験対策 > アルゴリズム > マージソート

マージソートについての説明

マージソートとは下記のような手順を繰り返して並べ替えを行うソートアルゴリズムをいいます。

  1. まず左端から2つの値をとり、その2つを小さい順に並べ替えます
  2. その右隣の2つの値をとり、その2つを小さい順に並べ替えます
  3. 上記1と上記2で並べ替えた値(合計で4つの値がありますね)を小さい順に並べかえます。
  4. 次に上記3の右隣の4つの数字を上記1,2,3と同じ手順で並べ替えをします。
  5. 上記3、4で並べ替えた値(合計で8つの値がありますね)を小さい順に並べ替えます。

このように、2つから4つ、4つから8つというように、「少ない個数の値を並べ替える」→「すでに並べ替えてある少ない個数の値を合体(マージ)して、より多い個数の値の並べ替える」という手順で並べ替えを行うのがマージソートの考え方です。

マージソートの具体例

それでは、マージソートの具体例として、「5 8 4 1 7 3 2 6」と適当に並んでいる数字を「1 2 3 4 5 6 7 8」というように並べ替える例を考えていきたいと思います。

上の説明では「下から積み上げていく」イメージで説明をしましたが、実際にプログラミングを組むときには、「上から左右均等に分割して」、その後に、「下から積み上げていく」という手順になります。

分割作業

まずは、すべてのグループが1個または2個の数字からなるように左右均等に分割していきます。

分割1段階目

並べかえる数字を半分に分割します(なお、2で割り切れない数の時、例えば9つの数字がある場合は4個と5個という感じでどちらかに、その余った分を含めます)

マージソートの分割1段階目

分割2段階目

左側4つの数字を半分に分割し、右側4つの数字も半分に分割します。

マージソートの分割2段階目

並べ替え作業

並べかえ1段階目

2個の数字をそれぞれ左側が小さい数字になるよう並べ替えます。

マージソートの並べかえ1段階目

並べかえ2段階目

4個の数字をそれぞれ左側が小さい数字になるよう並べ替えます。

マージソートの並べかえ2段階目

並べかえ3段階目

8個の数字をそれぞれ左側が小さい数字になるよう並べ替えます

マージソートの並べかえ3段階目

この並べかえの過程をひとつの図にまとめると下記のようになります。

マージソートの図解

マージソートの図解

イメージがつかめたでしょうか?

カテゴリ一覧
アルゴリズム
アルゴリズムとは  ソートアルゴリズム  バブルソート  インサーションソート  クイックソート  マージソート  ソートアルゴリズムを体感する