安定な比較ソート ssort(stable sort) (qs14) を作成しました
ssort の性能評価で悩んでいます。
https://ja.wikipedia.org/wiki/ソート
にあるように、ソートには安定なソートと安定でないソートがあります。
newlib の qsort のソースコードを読むと、伝統的なアルゴリズムによる実装です。
これは安定でないソートです。
一方、glibc の qsort のソースコードを読むと
その実装は、クイックソートではなくマージソートで実装されています。
マージソートは安定なソートです。
newlib・glibc の qsort の性能を比較すると、
ソート条件（キー値の分布・要素数・要素サイズ）により、速い/遅いが入れ替わります。
さて、私が用意したほとんどのソート条件において、ssort は glibc の qsort より高速です。
qs_glibc と ss14g1 を実行したときの 比較関数の呼出し回数・実行時間 を以下に示します。
各行の最後の数値がソート１回あたりの処理時間(10μ秒単位)です。
qs_glibc は、glibc の qsort を実験用に改造したものです。
使用したプログラムは https://github.com/kawamura1953/stable-sort にあります。
なぜ glibc の qsort はマージソートを採用しているのでしょうか？
「最悪計算時間が短いから」では補えないほど、平均計算時間が遅いと思うのですが・・・
何かご存じの方はお教えいただけないでしょうか。
----------------- benchmark.txt begin --------------------
キー種別:同値なし 要素数:1万個 要素サイズ:8,20,400byte
qs_glibc d=-3 e=10000 s=8 R5000 M000:000:000:0: c=120451 602257294 T=12.01 240
ss14g1 d=-3 e=10000 s=8 R5000 M090:200:000:0: c=129440 647203516 T=12.51 250
qs_glibc d=-3 e=10000 s=20 R4000 M000:000:000:0: c=120451 481804645 T=30.00 750
ss14g1 d=-3 e=10000 s=20 R4000 M090:200:000:0: c=129432 517729992 T=10.22 255
qs_glibc d=-3 e=10000 s=400 R2000 M000:000:000:0: c=120449 240899735 T=10.86 543
ss14g1 d=-3 e=10000 s=400 R2000 M090:200:000:0: c=129414 258828893 T=10.34 517
キー種別:100種 要素数:1万個 要素サイズ:8,20,400byte
qs_glibc d=100 e=10000 s=8 R6000 M000:000:000:0: c=120211 721269066 T=13.13 219
ss14g1 d=100 e=10000 s=8 R6000 M090:200:000:0: c=62523 375140861 T=8.41 140
qs_glibc d=100 e=10000 s=20 R5000 M000:000:000:0: c=120211 601058260 T=35.97 719
ss14g1 d=100 e=10000 s=20 R5000 M090:200:000:0: c=62523 312616709 T=7.11 142
qs_glibc d=100 e=10000 s=400 R2000 M000:000:000:0: c=120212 240424496 T=10.12 506
ss14g1 d=100 e=10000 s=400 R2000 M090:200:000:0: c=62504 125008089 T=7.54 377
キー種別:2種 要素数:1万個 要素サイズ:8,20,400byte
qs_glibc d=2 e=10000 s=8 R8000 M000:000:000:0: c=94725 757804948 T=12.18 152
ss14g1 d=2 e=10000 s=8 R8000 M090:200:000:0: c=15120 120964685 T=4.74 59
qs_glibc d=2 e=10000 s=20 R8000 M000:000:000:0: c=94725 757804948 T=43.37 542
ss14g1 d=2 e=10000 s=20 R8000 M090:200:000:0: c=15120 120964685 T=4.87 61
qs_glibc d=2 e=10000 s=400 R3000 M000:000:000:0: c=94732 284197358 T=12.68 423
ss14g1 d=2 e=10000 s=400 R3000 M090:200:000:0: c=15121 45364669 T=7.61 254
キー種別:10種 要素数:1万,10万,100万個 要素サイズ:1000byte
qs_glibc d=10 e=10000 s=1000 R2000 M000:000:000:0: c=116416 232833027 T=13.87 693
ss14g1 d=10 e=10000 s=1000 R2000 M090:200:000:0: c=30010 60020710 T=10.70 535
qs_glibc d=10 e=100000 s=1000 R100 M000:000:000:0: c=1479708 147970872 T=10.25 10247
ss14g1 d=10 e=100000 s=1000 R100 M090:200:000:0: c=291330 29133013 T=7.25 7254
qs_glibc d=10 e=1000000 s=1000 R10 M000:000:000:0: c=17952422 179524224 T=12.71 127130
ss14g1 d=10 e=1000000 s=1000 R10 M090:200:000:0: c=2911052 29110528 T=8.52 85180
================= benchmark.txt end ====================
各行の最後の数値がソート１回あたりの処理時間(10μ秒単位)です