Internet Explorerよりも速くソートできたよ：コーディングに役立つ！ アルゴリズムの基本（5）（1/4 ページ）

プログラマたるものアルゴリズムとデータ構造は知っていて当然の知識です。しかし、教科書的な知識しか知らなくて、実践的なプログラミングに役立てることができるでしょうか（編集部）

[山下寛人，オイシックス株式会社]

　第4回「Internet Explorerよりも速くソートできるかな」では、選択ソート、バブルソート、シェルソート、クイックソートを実装して、IE組み込みのソート機能よりも速くソートできるかを試しました。残念ながら、いまのところ組み込みのソートよりも速くソートできていません。しかし徐々に差は縮まっています。

　ソートのアルゴリズムは、まだまだたくさんの種類があります。代表的なものだけでもまだいくつか残っていますので、今回はこれらを実装して、IE組み込みのソート機能と速度を比較してみましょう。だんだん複雑になってきますが、頑張りましょう。

マージソート―小さく考え、大きく回答

　ある問題を解く際のアプローチに、分割統治法と呼ばれる手法があります。問題をいくつかの部分に分割し、分割された小さな問題を解き、その結果を再度まとめて全体の問題を解くというものです。

　マージソートは分割統治法の典型的な例としてよく取り上げられます。本連載でもハノイの塔やクイックソートを紹介しましたが、これらも分割統治法を用いたアルゴリズムです。分割統治法を用いたアルゴリズムは再帰とも深い関係があります。

　マージソートは次の手順でソートを行うアルゴリズムです。配列を2つの部分配列に分割します。分け方は半々です。半分に分けた配列をさらに半分に分けます。これをどんどん繰り返していくと最終的に1つ1つの要素に分解されます。

　全部分解したら今度は要素を統合（マージ）していきます。1つの要素と1つの要素を統合します。統合するときに要素同士を比較して小さい順になるようにします。要素2つの配列に統合したらほかの部分配列と統合していきます。全部統合するとソートされた状態になります。

イラストで見るマージソート

　実際の例を見てみましょう。次のような配列があったとします。

　配列を分割していきます。

　分割した要素を統合していきます。左側の5と4に着目します。5と4を比較し、4の方が小さいので4を先にピックアップします。次に残った5を付け加えます。

　同じ要領で要素を統合していきます。

　今度は2つずつの部分配列を相互に比較しながら統合していきます。まず4と3に着目します。4と3を比較し、3の方が小さいので3をピックアップします。

　右の配列のインデックスを1つ進め、4と8を比較します。4の方が小さいので4をピックアップします。

　左の配列のインデックスを1つ進め、5と8を比較します。5の方が小さいので5をピックアップします。最後に8が残るので8を付け加えます。

　あとは同じ要領でソートしながら部分配列を統合していきます。

　全部ソートできました。

　マージソートは細かい単位に区切ってソートしていくため、全体を総当たり的に比較・ソートしていくやり方より効率的にソートできます。部分に分けて処理するため、少し工夫すれば複数のコンピュータで分散処理させることもできます。