１０．ソーティング（マージソート）

１０．１．マージ

ソーティングされた複数のデータをまとめて、１つのソーティングしたデータにすることをマージ（merge,併合）と呼びます。

ソーティングした大きなデータを更新するには、新しいデータを追加した後で全体をソーティングするより、追加分のデータだけ別にソーティングして、すでにソーティングしてある古いデータとマージする方が遥かに速い事が知られています。ソーティングせずに追加する場合は、追加データ全てに関して、どこに挿入するか前から順に調べていかなければならないのに対し、ソーティング済みの場合は、前のデータを挿入した位置から後を順に調べていけばよいので、全体として調べる回数が減ります。

１０．２．マージソート

マージを利用したソーティング手法をマージソートと呼びます。マージソートはどのような場合でも計算量がO(nlogn)ですむ、高速なソーティングアルゴリズムです。下図は8つのデータをソーティングする時を例にした概念図です。まず配列内部のデータを4つずつ前半と後半に分割します。そして、それぞれをソーティングし最後にマージして１つに合わせます。

その際、それぞれのソーティングにもマージソートを利用します。したがって実際には下図のように、データが1つ単位になるまで再帰的に分割し、その後再帰的にマージを繰り返していく形になります。

（実習課題）

以下のプログラムを作成しなさい。

• 乱数発生プログラムで生成した数字を読み込み、それに対してマージソートを実行する。
• （ヒント）再帰呼び出しを利用する。
• （ヒント）マージの際のソーティングは、「ソーティング済みの2列の先頭データの内、小さい方のデータを取り出す」という作業を繰り返すイメージ。

1　2