イントロソートも書いてみた(introsort in C#)

バッファを使わないマージソートとバッファを使うマージソートのついでにイントロソートもSTLportからパクってみた。

STLportの_algo.c, _heap.h, _heap.cの__introsort_loop, __unguarded_partition, __final_insertion_sort, __unguarded_linear_insert, __partial_sort, __make_heap, __adjust_heap, __push_heap_aux, __pop_heap_aux, sort_heapあたりをC#で書いただけ。
かなり手抜きだと思う。マージソートとの速度差をみたいだけだから。

結果は次の通り。
Array.Sortの十数倍の時間がかかっている。バッファを使用するマージソートよりは多少速い。
ソート対象を配列からList<T>に変更するだけで数倍良くなるはずだから後でまとめて試してみる。
今になって基数ソート(radix sort)がかなり速いということを実感。

size: 1000
IntroSorter.Sort: 20622 (18.78)
Array.Sort: 1098 (1.00)
size: 10000
IntroSorter.Sort: 139073 (10.98)
Array.Sort: 12667 (1.00)
size: 100000
IntroSorter.Sort: 1771360 (12.22)
Array.Sort: 144995 (1.00)
size: 1000000
IntroSorter.Sort: 21275858 (12.85)
Array.Sort: 1656005 (1.00)

ksksts / junk / source — bitbucket.org