【日常のアルゴリズム】出席番号順ゲームでいち早く並んでみる（マージソート）

日常のアルゴリズムを体感するシリーズ。今回はソートアルゴリズムの中でも基本よりは少しレベルの上がった「マージソート」について解説します。お題について、今回は「出席番号順ゲーム」にしてチャレンジしてみましょう。

マージソートとは

マージソートは「分割と結合」を繰り返すことで並び替え行うアルゴリズムです。

例えば、1から5までの数字がランダムで配置された状態から、最終的に「左から小さい値から大きな値に並び替える」ことをゴールとして並び替え（ソート）を行ってみましょう。

マージソートはまず「分割」からはじめます。例題の値は1から5までの奇数ですが、最小になるまで、気にせず値を分割していきます。

分割が終わったら次は入れ替えを行いながら、入れ替えた値を「結合」していきます。つぎの例ではまず、5と2および4と3を入れ替えます。イメージとしては、並び替えを行いながら元のグループに戻していくような感じの作業です。

同様に、最初のグループに戻しながら値を入れ替えていくと、並び替えが完了します。バブルソートや選択ソートとは異なり並び替えの対象を分割していくので、並び替えの処理は早いといわれています。

マージソートを体験する「出席番号順ゲーム」

マージソートを体験するには決まった番号を使ってみるのが良いでしょう。今回は生徒児童が必ず「異なる値」で「規則性のある値」でもある「出席番号」を使った並び替えをゲーム形式で行ってみたいと思います。

広い場所があればクラス全員で、広い場所が確保できない場合は8名1グループ程度で出席番号の小さい順にマージソートを実施します。要領としては、最小まで分割（1名単位になるまで分割）を繰り返したあとに、隣同士の人と出席番号を確認し、並び替えを行っていきます。人数にもよりますが、8名であれば3回の分割と、3回の結合で並び替わることを確認できると思います。

マージソートは安定したアルゴリズム

マージソートは分割と統合を繰り返すという仕組み上、複雑なようにも感じますが、実は規則性があるアルゴリズムであるため、安定的でかつ速度も早いと言われています。出席番号順ゲームも楽しいと思うのでぜひ試してみてください。