マージソート

●ITヒント5 ‐ マージ

●同一物あるいは類似物を近づけたり、マージしたり、まとめて並列動作させたりしてみる

●作業を連続または並行させたり、同時に行ったりしてみる

例:　マージソート

　汎用のソートアルゴリズムではクイックソートアルゴリズムが最速だが、このアルゴリズムではデータに対して順次アクセスしかできない連結リストなどの場合、ランダムアクセスによるピボット選択ができない。

　連結リストのソートに最適化されたマージソートアルゴリズム（下図）を利用すれば、比較ベースのアルゴリズムなので、安定しているし、ソート結果における同値要素の順番も保たれます。

マージソートの基本的な考え方： 
1. 未ソートのリストをほぼ同じ長さの二つのサブリストに繰り返し分割する　
2. サブリストをソートする　
3. ソートされたサブリストを繰り返しマージしてソート済みリストを生成する


出典： TRIZ Technology for Innovation ( http://www.trizsolution.com )