バッファを使用するマージソートも書いてみた(merge sort with buffer in C#)

in-place merge sortをEQUATEC Profilerでプロファイルしてみたけど特におかしいと感じるところは見つからず、結局マージ回数が多すぎじゃないかと思う（あとお手玉Rotatenってやっぱり速いのかなと）。
in-placeじゃないアルゴリズムとの比較をするためにSTLportの_algo.cのstable_sortから__stable_sort_adaptive, __merge_sort_with_buffer, __chunk_insertion_sort, __merge_sort_loop, mergeあたりを辿って、ソート対象の要素個数分のバッファを使用するマージソートをC#で書いてみた。
結果は下記の通り。in-place merge sortよりは良い。でもまだArray.Sortの十数倍の時間がかかっている。
いろいろ小賢しいことをやっているからもっとシンプルな素直なコードを書いてみたほうがいいかもしれない。

size: 1000
InPlaceMergeSorter.Sort: 37314 (33.24)
MergeSorter.Sort: 21869 (19.48)
Array.Sort: 1122 (1.00)
size: 10000
InPlaceMergeSorter.Sort: 502465 (39.24)
MergeSorter.Sort: 198861 (15.53)
Array.Sort: 12805 (1.00)
size: 100000
InPlaceMergeSorter.Sort: 7425488 (47.00)
MergeSorter.Sort: 2556782 (16.18)
Array.Sort: 157988 (1.00)
size: 1000000
InPlaceMergeSorter.Sort: 98928451 (58.09)
MergeSorter.Sort: 31298754 (18.38)
Array.Sort: 1703143 (1.00)

ksksts / junk / source — bitbucket.org