sqsortの特徴は、同じキー値(県名・男女など)が現れる場合に極めて高速なことです。

また、マージソート的な部分がないにもかかわらず、安定性があることです。

以下では、
「安定」とは、「キー値が同じ要素は、ソート前の順序をソート後も維持する」こととします。
「安全」とは、「悪意のある配列により、異常に長いソート時間を発生させることが不可能」
　　　　　　　　なこととします。

sqsort では「安全」を実現するために、
clock ( ) 関数を再現性のない乱数発生器として使用し、ピボットの候補を決定します。
これにより、理論上の最悪計算時間 $O(n^2)$ は変化しませんが、
「悪意のある配列を作ることは不可能」となります。

sqsort は大雑把にいうと、対象配列 ( ptr ) と補助配列 ( ptr2 ) で
次のような移動(Ａ,Ｂ)を繰り返します。

   ptr2:...............  →   ptr2:332223....77787  →  ptr2:332223....77787
   ptr :357358257257237  Ａ  ptr :5555...........  Ｂ  ptr :......5555.....

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

sqsort ( 約350行　.oファイル約12800byte ) は、
timsort ( 約1300行　.oファイル約31400byte ) よりかなりコンパクトです。
qsortを含めた３種類のソートを比較すると次の表のようになります。

	timsort	sqsort	qsort 非安定
速さ	△	◎	◎
作業領域	△	△	◎
安定性	○	○	×
安全性	◎	○	×
サイズ	×	○	◎

処理時間を測定したもの ( benchmark.txt ) を以下に記載します。
各行の最後の数値がソート１回あたりの処理時間です。
48行目で my_qsort より sqsort が少し遅くなっていますが、
これは、sqsortの「安定性」実現のために、余分な要素の移動が起きたためです。

----------------- benchmark.txt begin -------------------- 
 
　　キー:同値なし 要素:1万個　要素サイズ:8,20,80,1000byte 
my_qsort d=-3 e=10000 s=8 R4000 M000:000:000:0: c=136798  547192609 T=3.77   94 
timsort  d=-3 e=10000 s=8 R4000 M000:000:000:0: c=120390  481561920 T=5.38  134 
sqsort   d=-3 e=10000 s=8 R4000 M000:000:000:0: c=141438  565754586 T=3.27   82 
 
my_qsort d=-3 e=10000 s=20 R3000 M000:000:000:0: c=136804  410413695 T=4.73  158 
timsort  d=-3 e=10000 s=20 R3000 M000:000:000:0: c=120390  361170762 T=10.73  358 
sqsort   d=-3 e=10000 s=20 R3000 M000:000:000:0: c=141434  424304000 T=3.08  103 
 
my_qsort d=-3 e=10000 s=80 R3000 M000:000:000:0: c=136804  410413695 T=3.61  120 
timsort  d=-3 e=10000 s=80 R3000 M000:000:000:0: c=120390  361170762 T=13.92  464 
sqsort   d=-3 e=10000 s=80 R3000 M000:000:000:0: c=141416  424249151 T=3.36  112 
 
my_qsort d=-3 e=10000 s=1000 R600 M000:000:000:0: c=136845   82107153 T=3.48  581 
timsort  d=-3 e=10000 s=1000 R600 M000:000:000:0: c=120389   72233808 T=12.56 2094 
sqsort   d=-3 e=10000 s=1000 R600 M000:000:000:0: c=141351   84810864 T=1.69  281 
 
　キー種別:100種　要素:1万個　要素サイズ:8,20,80,1000byte 
my_qsort d=100 e=10000 s=8 R6000 M000:000:000:0: c=62893   377363710 T=2.42   40 
timsort  d=100 e=10000 s=8 R6000 M000:000:000:0: c=103239  619435932 T=7.33  122 
sqsort   d=100 e=10000 s=8 R6000 M000:000:000:0: c=62388   374330081 T=2.23   37 
 
my_qsort d=100 e=10000 s=20 R3000 M000:000:000:0: c=62926   188780724 T=2.52   84 
timsort  d=100 e=10000 s=20 R3000 M000:000:000:0: c=103239  309719470 T=8.59  286 
sqsort   d=100 e=10000 s=20 R3000 M000:000:000:0: c=62402   187208373 T=1.74   58 
 
my_qsort d=100 e=10000 s=80 R4000 M000:000:000:0: c=62922   251691334 T=2.40   60 
timsort  d=100 e=10000 s=80 R4000 M000:000:000:0: c=103240  412961519 T=15.39  385 
sqsort   d=100 e=10000 s=80 R4000 M000:000:000:0: c=62376   249505124 T=2.56   64 
 
my_qsort d=100 e=10000 s=1000 R500 M000:000:000:0: c=62919    31459751 T=2.17  434 
timsort  d=100 e=10000 s=1000 R500 M000:000:000:0: c=103239   51619835 T=9.62 1925 
sqsort   d=100 e=10000 s=1000 R500 M000:000:000:0: c=62401    31200583 T=1.19  237 
 
　　キー種別:2種　要素:1万個　要素サイズ:8,20,80,1000byte 
my_qsort d=2 e=10000 s=8 R12000 M000:000:000:0: c=15020   180242977 T=1.16   10 
timsort  d=2 e=10000 s=8 R12000 M000:000:000:0: c=45262   543150430 T=7.89   66 
sqsort   d=2 e=10000 s=8 R12000 M000:000:000:0: c=15014   180176778 T=1.00    8 
 
my_qsort d=2 e=10000 s=20 R7000 M000:000:000:0: c=15020   105142708 T=2.20   31 
timsort  d=2 e=10000 s=20 R7000 M000:000:000:0: c=45263   316841085 T=8.08  115 
sqsort   d=2 e=10000 s=20 R7000 M000:000:000:0: c=15046   105326276 T=0.95   14 
 
my_qsort d=2 e=10000 s=80 R6000 M000:000:000:0: c=15020    90123066 T=1.20   20 
timsort  d=2 e=10000 s=80 R6000 M000:000:000:0: c=45263   271579105 T=9.36  156 
sqsort   d=2 e=10000 s=80 R6000 M000:000:000:0: c=15015    90091994 T=1.72   29 
 
my_qsort d=2 e=10000 s=1000 R400 M000:000:000:0: c=15021     6008462 T=0.97  242 
timsort  d=2 e=10000 s=1000 R400 M000:000:000:0: c=45265    18106265 T=3.95  988 
sqsort   d=2 e=10000 s=1000 R400 M000:000:000:0: c=15010     6004395 T=0.77  192 
 
 
　 キー:同値なし　百～百万要素　要素サイズ:200byte 
my_qsort d=-3 e=100 s=200 R200000 M000:000:000:0: c=644     128893028 T=1.67    1 
timsort  d=-3 e=100 s=200 R200000 M000:000:000:0: c=538     107623993 T=4.89    2 
sqsort   d=-3 e=100 s=200 R200000 M000:000:000:0: c=691     138210336 T=1.38    1 
 
my_qsort d=-3 e=1000 s=200 R14000 M000:000:000:0: c=10064   140901071 T=1.67   12 
timsort  d=-3 e=1000 s=200 R14000 M000:000:000:0: c=8682    121560507 T=5.39   39 
sqsort   d=-3 e=1000 s=200 R14000 M000:000:000:0: c=10530   147423146 T=1.16    8 
 
my_qsort d=-3 e=10000 s=200 R1000 M000:000:000:0: c=136826  136826241 T=1.59  159 
timsort  d=-3 e=10000 s=200 R1000 M000:000:000:0: c=120389  120389545 T=6.25  625 
sqsort   d=-3 e=10000 s=200 R1000 M000:000:000:0: c=141353  141353954 T=1.17  117 
 
my_qsort d=-3 e=100000 s=200 R60 M000:000:000:0: c=1727630  103657844 T=1.50 2498 
timsort  d=-3 e=100000 s=200 R60 M000:000:000:0: c=1534821   92089290 T=5.00 8333 
sqsort   d=-3 e=100000 s=200 R60 M000:000:000:0: c=1777877  106672678 T=1.62 2708 
 
my_qsort d=-3 e=1000000 s=200 R7 M000:000:000:0: c=20971928  146803502 T=2.14 30557 
timsort  d=-3 e=1000000 s=200 R7 M000:000:000:0: c=18640815  130485706 T=7.12 101786 
sqsort   d=-3 e=1000000 s=200 R7 M000:000:000:0: c=21374068  149618482 T=2.70 38629 
 
=================  benchmark.txt end  ==================== 
my_qsort：ベンチマークテスト実行の計算機上の C ライブラリの qsort 
timqsort：https://github.com/patperry/timsort/ の timsort 
sqsort　：今回公開した sqsort 
d=キー種類 e=要素数 s=要素サイズ R繰返し回数 c=比較回数/R T=処理秒数 
各行の最後の数値がソート１回あたりの処理時間(10μ秒単位)です