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

１０．１．マージ

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

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

１０．２．マージソート

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