マージソートとは

図のように既にソートされた（小さい順に並んでいる）2つの数列の頭から1個ずつを取り出して比較し、小さい方から順に新しい数列に詰めていくという方法を使って、2つのソート済み数列を1つの大きなソート済み数列に統合していく方法です。

最初は

このように要素が1個だけの数列から始めて、出来上がった要素が2つの数列どうしでさらにマージソート、というように繰り返して徐々に数列を長くしていきます。

繰り返すとトーナメントを勝ち上がるように徐々に要素同士の大小関係が確定していきます。

従って、2つの数列から1個ずつ取り出している間は、片方をクリックしたとき、その要素の次に並んでいた要素が自動的に前に出てきます。

要素の比較が終わって比較用の数列が空っぽになると、次の新しい数列の評価に移るので両方のボタンが同時に新しい要素に切り替わります。

ソートが進むにつれて数列は長くなるので、段々と片方だけ変わるパターンが多くなっていき、しかも既にある程度ソートされたもの同士を比較するので微妙な判断を迫られる頻度も徐々に増えていきます。

以上、マージソートについてのお話しでした。こんなことを考えながらクリックすると、徐々にソートが進んで数列が長くなっていく様子が実感できて楽しいです。

ちなみに、マージソートとは2つの数列を合体させる（マージする）うちにソートが完了するからそういう名前が付いているそうです。諸々の事情でライバルの“クイックソート”より採用は少ないですが、最速のソートアルゴリズムの一種です。

余談: ライバルのクイックソートはソートの前半で間違った大小を付けると、ソート結果に大きく響くので、人間が判定するような並び替えには向いてないんだと思います。

おまけ

ソートした本人の感想としては、みすちーの順位高すぎでね？です。

コメント投稿