C#でのソートアルゴリズムのまとめ(sort algorithms in C#)

stereopsis : graphics : radix tricksやSTLportのソースをパクったりしたC#でのソートのまとめ。

それぞれのアルゴリズムとか関連エントリとか。

• ksksts's blog: C#で実装したradix sortとArray.Sortのquick sortとの比較
• ksksts's blog: C#で符号付整数／浮動小数点数対応の基数ソート(radix sort)
• ksksts's blog: C#でin place merge sortを書いてみたらかなり遅かった 
• ksksts's blog: バッファを使用するマージソートも書いてみた(merge sort with buffer in C#) 
• ksksts's blog: イントロソートも書いてみた(introsort in C#)

配列に対するソートとList<T>に対するソートに対するソートとの差やEnumerable.OrderBy メソッド (System.Linq)とかも含めた測定結果は次の通り。

size: 1000
Array.Sort: 1186 (1.00)
List.Sort: 1050 (0.89)
Array.OrderBy: 6592 (5.56)
List.OrderBy: 3305 (2.78)
CombSort Array: 31971 (26.94)
CombSort List: 6909 (5.82)
NumberRadixSorter.Sort Array: 4943 (4.17)
NumberRadixSorter.Sort List: 2291 (1.93)
InPlaceMergeSorter.Sort Array: 40326 (33.98)
InPlaceMergeSorter.Sort List: 12642 (10.65)
MergeSorter.Sort Array: 24463 (20.61)
MergeSorter.Sort List: 9604 (8.09)
IntroSorter.Sort Array: 22909 (19.30)
IntroSorter.Sort List: 4158 (3.50)

size: 10000
Array.Sort: 12771 (1.00)
List.Sort: 12497 (0.98)
Array.OrderBy: 41599 (3.26)
List.OrderBy: 41126 (3.22)
CombSort Array: 465802 (36.47)
CombSort List: 101879 (7.98)
NumberRadixSorter.Sort Array: 27803 (2.18)
NumberRadixSorter.Sort List: 22234 (1.74)
InPlaceMergeSorter.Sort Array: 553976 (43.38)
InPlaceMergeSorter.Sort List: 202408 (15.85)
MergeSorter.Sort Array: 224039 (17.54)
MergeSorter.Sort List: 128939 (10.10)
IntroSorter.Sort Array: 158357 (12.40)
IntroSorter.Sort List: 52881 (4.14)

size: 100000
Array.Sort: 146888 (1.00)
List.Sort: 145938 (0.99)
Array.OrderBy: 520984 (3.55)
List.OrderBy: 518649 (3.53)
CombSort Array: 6044506 (41.15)
CombSort List: 1311650 (8.93)
NumberRadixSorter.Sort Array: 279857 (1.91)
NumberRadixSorter.Sort List: 218608 (1.49)
InPlaceMergeSorter.Sort Array: 8215845 (55.93)
InPlaceMergeSorter.Sort List: 2860999 (19.48)
MergeSorter.Sort Array: 2931658 (19.96)
MergeSorter.Sort List: 1869126 (12.72)
IntroSorter.Sort Array: 1945971 (13.25)
IntroSorter.Sort List: 658093 (4.48)

size: 1000000
Array.Sort: 1666666 (1.00)
List.Sort: 1668472 (1.00)
Array.OrderBy: 6961424 (4.18)
List.OrderBy: 6901036 (4.14)
CombSort Array: 76084478 (45.65)
CombSort List: 16674472 (10.00)
NumberRadixSorter.Sort Array: 2864637 (1.72)
NumberRadixSorter.Sort List: 2245710 (1.35)
InPlaceMergeSorter.Sort Array: 110817348 (66.49)
InPlaceMergeSorter.Sort List: 38880094 (23.33)
MergeSorter.Sort Array: 35271234 (21.16)
MergeSorter.Sort List: 20756358 (12.45)
IntroSorter.Sort Array: 24093398 (14.46)
IntroSorter.Sort List: 8047601 (4.83)

ksksts / junk / source — bitbucket.org

まとめ:

• 安定でないソートならArray.Sort メソッド (System)かList(T).Sort メソッド (System.Collections.Generic) 
• 安定なソートならEnumerable.OrderBy メソッド (System.Linq) 
• STLportのソースをパクった結果としては速い順にIntroSort（STLのstd::sort）, InPlaceMergeSort（STLのstd::stable_sortのバッファを使わない版）, MergeSort（STLのstd::stable_sortのバッファを使う版）。そしてRadixSort（基数ソート）はこいつらより速い。
• 配列の添字でのランダムアクセスはList<T>のインデクサでのアクセスより遅い？（これはIList<T>を経由しているのが原因だったみたい ksksts's blog: 配列やList<T>をIList<T>型のインデクサでアクセスするとパフォーマンスが悪い(don't use IList<T>'s indexer)）