マージソートの高速化を試みた

６月６日の日記。

午後０時（それは正午である。）に起きた……。

きのうに続き、出かけることはなかった。

『アルゴリズムイントロダクション』の勉強が２日間停滞していて、未だにクイックソートを始められていない。（まあ、クイックソートは以前実装したことがあるので、たやすく習得できるとは思うけど。）（そういう問題ではない。）

夕方はなぜかかなり体がだるかった。

マージソートの高速化を試みた。

一つは、マージソートの再帰が深くなって処理対象の要素数が十分に小さく（50個程度がいいらしい。）なったとき、それ以降はマージソートの再帰を行なうのでなく挿入ソートでちょくせつソートするようにするということ。マージソートの実行時間は $Ο(n \lg n)$ ，挿入ソートの実行時間は $Ο(n^2)$ で、 $n$ （要素の数）が十分に大きければ、処理時間はマージソートのほうが小さくなる（漸近的に高速である。）。

しかしマージソートは処理のオーバヘッドが大きく、 $n$ が十分に小さければ挿入ソートのほうが高速だ。そのため、複数のアルゴリズム（ここではマージソートと挿入ソート）を適当に切り替えることで全体的な実行時間が向上する。すばらしい！

もう一つはマージソートを並列化するということ。

マージソートではソート対象（リスト）を再帰的に半分ずつの小分けにしてソートを行なう。（ということで、小分けのレベルが深くなって行くとリストの要素の数は元の数から $\frac{1}{2}$ , $\frac{1}{4}$ , $\frac{1}{8}$ ,...　というふうに小さくなって行く。）小分けに対する処理はそれぞれ独立しているので、並列処理が行なえる。