より高速なqsortクイックソート qs19

2019年にqsort(qs15)を公開しました。
　　　　https://qiita.com/t-kawa/items/631564a703e20dceed24

2020～2021年に安定なクイックソートsqsort(ss18)を公開しました。
　　　　https://qiita.com/t-kawa/items/dc15243e160a4af90518

qsort は timsort や sqsort より高速です。( timsort < sqsort < qsort )
ただし、qsortは非安定です。

sqsort開発の過程で、
　　「安定性がなくても、とにかく高速なソートが必要だ」
と感じました。
今回、sqsortで使用した方法で、qs15より約5%高速なqs19を開発しました。

qsort(qs19)のソースコード・ベンチマークプログラムなどは
　　　　http://ww51.tiki.ne.jp/~srr-cake/qsort/qs19/ 　　にあります。

qsort19.cのソースコードは約500行です。
timsort ( 約1300行 ) よりかなりコンパクトです。

言語Cの標準ライブラリのqsortと今回のqsort19の処理時間を
測定したものを以下に記載します。
まだまだ多くの標準ライブラリのqsortが低速であると思われます。
ご興味がおありの方は、上記のベンチマークプログラムを動かして
その結果をこのQiitaのコメント欄に掲示して頂けないでしょうか。

----------------- benchmark.txt begin -------------------- 
 
　　キー:同値なし 要素:1万個　要素サイズ:8または4,20,80,1000byte 
qsort    d=-3 e=10000 s=8 R4000 M000:000:000:0: c=136763  547054643 T=3.75   94 
qsort19  d=-3 e=10000 s=8 R4000 M120:580:000:0: c=128058  512234423 T=3.27   82 
 
qsort    d=-3 e=10000 s=20 R3000 M000:000:000:0: c=136748  410244182 T=4.73  158 
qsort19  d=-3 e=10000 s=20 R3000 M120:580:000:0: c=128053  384160670 T=3.00  100 
 
qsort    d=-3 e=10000 s=80 R3000 M000:000:000:0: c=136748  410244182 T=3.61  120 
qsort19  d=-3 e=10000 s=80 R3000 M120:580:000:0: c=128053  384160670 T=3.31  110 
 
qsort    d=-3 e=10000 s=1000 R600 M000:000:000:0: c=136776   82066150 T=3.47  578 
qsort19  d=-3 e=10000 s=1000 R600 M120:580:000:0: c=128090   76854257 T=1.69  281 
 
　キー種別:100種　要素:1万個　要素サイズ:8または4,20,80,1000byte 
qsort    d=100 e=10000 s=8 R6000 M000:000:000:0: c=62894   377366851 T=2.44   41 
qsort19  d=100 e=10000 s=8 R6000 M120:580:000:0: c=60849   365096092 T=2.28   38 
 
qsort    d=100 e=10000 s=20 R3000 M000:000:000:0: c=62889   188668276 T=2.52   84 
qsort19  d=100 e=10000 s=20 R3000 M120:580:000:0: c=60841   182523251 T=1.36   45 
 
qsort    d=100 e=10000 s=80 R4000 M000:000:000:0: c=62897   251590917 T=2.39   60 
qsort19  d=100 e=10000 s=80 R4000 M120:580:000:0: c=60844   243378572 T=2.06   52 
 
qsort    d=100 e=10000 s=1000 R500 M000:000:000:0: c=62849    31424752 T=2.19  438 
qsort19  d=100 e=10000 s=1000 R500 M120:580:000:0: c=60866    30433364 T=1.16  231 
 
　　キー種別:2種　要素:1万個　要素サイズ:8または4,20,80,1000byte 
qsort    d=2 e=10000 s=8 R30000 M000:000:000:0: c=15020   450617436 T=2.81    9 
qsort19  d=2 e=10000 s=8 R30000 M120:580:000:0: c=15051   451545559 T=2.42    8 
 
qsort    d=2 e=10000 s=20 R13000 M000:000:000:0: c=15019   195259918 T=4.09   31 
qsort19  d=2 e=10000 s=20 R13000 M120:580:000:0: c=15051   195672706 T=1.20    9 
 
qsort    d=2 e=10000 s=80 R12000 M000:000:000:0: c=15019   180239524 T=2.44   20 
qsort19  d=2 e=10000 s=80 R12000 M120:580:000:0: c=15051   180619742 T=1.22   10 
 
qsort    d=2 e=10000 s=1000 R1200 M000:000:000:0: c=15020    18024163 T=2.90  242 
qsort19  d=2 e=10000 s=1000 R1200 M120:580:000:0: c=15082    18098625 T=0.84   70 
 
 
　 キー:同値なし　百～百万要素　要素サイズ:200byte 
qsort    d=-3 e=100 s=200 R400000 M000:000:000:0: c=644     257805086 T=3.30    1 
qsort19  d=-3 e=100 s=200 R400000 M120:580:000:0: c=605     242260779 T=2.44    1 
 
qsort    d=-3 e=1000 s=200 R28000 M000:000:000:0: c=10064   281797331 T=3.35   12 
qsort19  d=-3 e=1000 s=200 R28000 M120:580:000:0: c=9362    262156451 T=2.33    8 
 
qsort    d=-3 e=10000 s=200 R2000 M000:000:000:0: c=136727  273455402 T=3.25  162 
qsort19  d=-3 e=10000 s=200 R2000 M120:580:000:0: c=128089  256178193 T=2.45  123 
 
qsort    d=-3 e=100000 s=200 R120 M000:000:000:0: c=1729580  207549609 T=3.00 2500 
qsort19  d=-3 e=100000 s=200 R120 M120:580:000:0: c=1626865  195223804 T=2.77 2305 
 
qsort    d=-3 e=1000000 s=200 R11 M000:000:000:0: c=20994830  230943134 T=3.33 30245 
qsort19  d=-3 e=1000000 s=200 R11 M120:580:000:0: c=19665513  216320653 T=3.08 27982 
 
=================  benchmark.txt end  ==================== 
qsort   ：ベンチマークテスト実行の計算機上の C ライブラリの qsort 
qsort19 ：今回公開した qsort19の qsort 
d=キー種類 (d=-3は、ユニーク乱数。d=kは、rand()%k でキーを算出。 
e=要素数 s=要素サイズ R繰返し回数 c=比較回数/R T=処理秒数 
各行の最後の数値がソート１回あたりの処理時間(10μ秒単位)です