最近のソートは、クイックソートに代わってマージソートが主流のようです。
最大の理由は「安定」性にあると思われます。しかし、マージソートは
　（１）要素の移動回数が多い
　（２）同じキー値が複数現れる場合でも速度向上が十分には望めない
などの欠点があります。
#####このことから「安定」な qsort (Sqsort) (比較ソート) を作りました。
#####最大の特徴は、キー値に同じ値が現れる場合に極めて高速なことです。
Sqsortはjavaで記述してあり、同じくjavaで記述したTimSortより高速です。
大雑把にいうと、Sqsortは補助配列(bas2)と対象配列(base)で
以下のような移動を繰り返します。

   bas2:...............  →  bas2:5555......77787  →  bas2:..........77787
   base:357358257257237  Ａ base:332223.........  Ｂ  base:3322235555.....

プログラム(約150行 classファイル 3164byte) は最後に記載します。
TimSort(約900行 classファイル 8801byte) よりかなりコンパクトです。
処理時間を測定したものを以下に記載します。

    ソート名   キーの種類  　要素数　 　繰返し回数　処理時間(秒)
     TimSort    d=-3      e=10000     R=2000     C=8.21 
     Sqsort     d=-3      e=10000     R=2000     C=5.65 
                                                            
     TimSort    d=100     e=10000     R=2000     C=6.69 
     Sqsort     d=100     e=10000     R=2000     C=2.81 
                                                            
     TimSort    d=2       e=10000     R=6000     C=7.41 
     Sqsort     d=2       e=10000     R=6000     C=2.09 
 
      d=-3:キーの重複なし　d=100:キーが100種類　d=2:キーが男女など         
      繰返し回数：処理時間の測定誤差を減らすためにソートを繰り返した回数

すべての場合で、Sqsort は TimSort より高速です。
より詳細な測定結果・ベンチマークプログラム・TimSort/Sqsortのソースコードなどは
　　　　http://ww51.tiki.ne.jp/~srr-cake/qsort/sqs18j/ 　　にあります。

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

Sqsort では「安全」を実現するために、ピボットの候補を
乱数(System.nanoTime())により決定しています。
これにより、最悪計算時間O(n^2)は変化しませんが、
元々その発生確率は非常に低いものです。
これまで長い間、C言語のnewlibライブラリのqsort()の実装において
最悪計算時間への配慮がなかったことが、その低さを示していると思います。
今回、最悪計算時間の発生確率は変わりませんが、
「悪意のある配列」を作ることは不可能になっていると思います。

以上３種類のソートを比較すると次の表のようになります。

	TimSort	Sqsort	qsort
速さ	△	○	◎
作業領域	△	△	◎
安定性	○	○	×
安全性	○	○	×

また、TimSortでは配列に内在するソート済み部分列を有効利用しますが、
Sqsortにその機能はありません。
代わりに、Sqsortは同じキー値が複数回現れる場合に高速です。
TimSortにこの機能はありません。
すなわち、県名別にソートしたり、男女を分けるためにソートする場合に
極めて高速です。
　

Sqsortでは、最悪計算時間や安全性の問題を、
乱数による確率の問題として扱おうとしています。
これについては、以下の記事で解説します。
　　「乱数でピボットを選択した qsort の最悪計算時間について」
　　　 https://qiita.com/t-kawa/items/3dfba10c407d1aede95d

以下が Sqsort のソースコードです。

/***************************************************/
/*         Sqsort   (stable qsort)                 */
/*                                                 */
/* by 河村 知行 (kawamura tomoyuki)    2021.2.27   */
/*             t-kawa@crux.ocn.ne.jp               */
/***************************************************/

// Sqsort は安定な比較ソート。TimSortより高速で,作業領域は2n(TimSortはn),安全性はほぼ同じ
/*
対象配列(base)と補助配列(bas2)(baseと同じ大きさ)を用いて安定なソートを行う。
以下のように Ａ,Ｂ 2段階で要素を移動する。ここで「5」はピボット(分割要素)を表している。

   bas2:...............  →  bas2:5555......77787  →  bas2:..........77787
   base:357358257257237  Ａ  base:332223.........  Ｂ  base:3322235555.....

移動Ａで、ピボットと同じ要素をbas2の左端に集め、5より小さい要素をbaseの左端に集め、
5より大きい要素をbas2の右端に集める。このとき77787は初期順序(元順)の逆順になっている。
移動Ｂの完了時点で5555はすでにソート完成状態の位置に収まっている。
Ｂ直後、5555以外の要素は、base上では元順に、bas2上では逆順に並んでいる。
次に332223の{所属フラグ(base/bas2)・先頭位置・末尾位置}をスタックに保存する。
これ以降、77787に対しbaseとbas2の意味を入れ替えて同じ処理を繰り返す。
部分配列が長さ15以下になれば挿入ソートを実施して部分配列のソートを完了し、次に
スタックから{フラグ(base/bas2)・先頭位置・末尾位置}を取り出して処理を続ける。
スタックが空になればソートを終了する。
*/
#define C(x,y)  {           x=(y);       }  /* ソート対象配列の要素のコピーに用いる */
#define S(x,y)  {T tmp=(x); x=(y); y=tmp;}  /* ソート対象配列の要素のスワップに用いる */

#define CMP(x,y)       cmp.compare((x),(y))
#define med3p(x,y,z)  (CMP(x,y)<=0 ? (CMP(y,z)<=0 ? y : (CMP(x,z)<=0 ? z : x)) : \
                                     (CMP(y,z)>=0 ? y : (CMP(x,z)<=0 ? x : z)) )

#define I(x) {x++;} /* 配列base,bas2の添字を増やす */
#define D(x) {x--;} /* 配列base,bas2の添字を減らす */

import java.util.Comparator;

class Sqsort {

static int L,R;        // L,Rは、baseまたはbas2上のソート対象となる領域[L～R]の左端と右端
static boolean flagB;  // [L～R]領域がbase上にあるときtrue、bas2上にあるときfalse
// popメソッド内で L,R,flagB へ代入できるように、sortメソッドのローカル変数からここへ移動した

//#define  base0  base  /*これを有効にすると、配列base0を複写しない。 32bitJVMでは有効の方が速い*/

@SuppressWarnings({"unchecked"})
public static <T> void sort( T[] base0, Comparator<? super T> cmp ) {//base0:ソート対象である配列
                                                                     //  cmp:要素の比較をする関数
 int l,r,m; //ptrB[L～R]間の要素をptrB[L～l],ptrR[r～R],ptrR[L～m]へ振り分ける。l領域 r領域 m領域
 T[] ptrB, ptrR; //flagBのとき ptrB==base ptrR==bas2、!flagBのとき ptrB==bas2 ptrR==base。
 int n,t,p;      // nは、現在ソート中の[L～R]領域の要素数。tは作業用。pはL～R間を移動する添字
 final long rndm = (System.nanoTime() & 0xFFFFFFFFFFFFL); //nanoTime()を乱数発生器として使用

 class StkElt {             //スタックをローカルクラスで実装
   boolean sB; int sL,sR;
   void push(boolean b, int l, int r) {      sB=b;     sL=l;     sR=r;}
   void pop ()                        {flagB=sB;     L=sL;     R=sR;  }
 }
 final int STK_LEN=32;      // base0.lengthの最大値は2^31-1なので３２で十分
 StkElt stk[] = new StkElt[STK_LEN];
 for (int i=0; i<STK_LEN; i++) stk[i] = new StkElt();
 int top = 0;               // スタックポインタの初期値
   
 int Z = base0.length;      // このsortメソッドに渡されたソート対象配列の要素数
#ifndef base0               /* 64bit JVM では、コピーした配列をソートした方が速いので次行を使用 */
 T[] base = (T[]) new Object[Z];   System.arraycopy(base0, 0, base, 0, Z);
#endif
 T[] bas2 = (T[]) new Object[Z];  //baseと対になって使用。ただし、m領域のコピー先は常にbase

 flagB=true; L=0; R=Z-1;

 //ここまでは、sortの１回の呼び出して１度だけ実行される

 for(;;) {
   for(;;) {//LOOP:
     if (R<L)  {                                 break;/*goto nxt;*/} //要素なし
     if (L==R) {{if (!flagB) C(base[L],bas2[L])} break;/*goto nxt;*/} //要素数１
     
     n = (R - L + 1);      /*要素数 n>=2 */

     if (n <= 15) { //挿入ソート   結果はbase上に作る   n==2でも動く  「15」は実験で得られた値
       if (flagB) { //ソート領域base[L～R]は 元順 になっている
         if (CMP(base[L],base[L+1])>0) S(base[L],base[L+1])
         for (r = L+2; r <= R; r++) {
           if (CMP(base[r-1],base[r])<=0) continue;
           T tmp=base[r]; C(base[r],base[r-1])
           for (l=r-2; L<=l && CMP(base[l],tmp)>0; l--) C(base[l+1],base[l])
           base[l+1]=tmp;
         }
       }else{       //ソート領域bas2[L～R]は 逆順 になっている
         if (CMP(bas2[R-1],bas2[R])<0) {C(base[L],bas2[R-1]) C(base[L+1],bas2[R])  }
         else                          {C(base[L],bas2[R])   C(base[L+1],bas2[R-1])}
         for (r = R-2; L <= r; r--) {
           t=L+(R-r);
           if (CMP(base[t-1],bas2[r])<=0) {C(base[t],bas2[r]) continue;}
           T tmp=bas2[r]; C(base[t],base[t-1])
           for (l=t-2; L<=l && CMP(base[l],tmp)>0; l--) C(base[l+1],base[l])
           base[l+1]=tmp;
         }
       }
       break; /*goto nxt;*/
     }

     if (flagB) {ptrB=base; ptrR=bas2;} else {ptrB=bas2; ptrR=base;}

     {//３点処理（３要素からピボットを選択　高速化のため９点処理や２７点処理の版もある）
       int rnd = (int)(rndm % ((n >> 1) - 2)); //nanoTime()を乱数発生器として使用
       T ll=ptrB[L+rnd], rr=ptrB[R-rnd],       //悪意ある攻撃を無効化するため、要素を乱数で選択
         mm=ptrB[L + (n >> 1)]; //中央の要素   //３点の内、定点が２点では悪意ある配列が作れてしまう

       T mmm=med3p(ll,mm,rr);                  //３点を比較して、mmmにピボットをセットする

     // l:ピボットより小さい要素(小要素)を次に置く所  r:大要素を次に置く所  m:同要素を次に置く所
     // ptrR[L～m]:左端からm領域を作る  ptrR[r～R]:の右端からr領域を作る(bas2上のr領域は逆順となる)
     // ptrB[L～l]:左端からl領域を作る  ptrB[L～R]:この全要素を左端からl領域,r領域,m領域へ振分ける
       l=m=p=L; r=R; 
       do {T pp=ptrB[p]; if ((t=CMP(pp,mmm)) < 0) {C(ptrB[l],pp) I(l)}
                         else if          (t > 0) {C(ptrR[r],pp) D(r)}
                         else                     {C(ptrR[m],pp) I(m)} I(p)} while(p<=R);
     }

     assert L<m;                    //m領域には少なくとも要素１個が配置される
     assert (l-L)+(m-L)+(R-r)==n;   //l領域,r領域,m領域の要素数の合計は ptrB[L～R]の要素数に等しい

     if (m-L == 1) {        //m領域をbase上のあるべき位置に移動する
       C(base[l],ptrR[L])   //要素数が１のときは、単純に代入（これは高速化のため。省略可能）
     }else{
       if (flagB) {
         System.arraycopy(bas2, L, base, l, m-L);                 //bas2上のm領域は常に元順
       }else{
         if (m<=l) {
           p=l; do {D(m) C(base[p],base[m]) I(p)} while (L<m);    //base上のm領域は常に逆順
         }else{
           for (t=m-1, p=l; p<t;) {S(base[p],base[t]) I(p) D(t)}  //m領域とその移動先が重なるとき
           for (p=m, m=l; L<m;) {D(m) C(base[p],base[m]) I(p)}
         }
       }
     }

     if (l-L < R-r) {stk[top++].push(!flagB,r+1,R); /*flagB=flagB;*/ R=l-1;} /*左を先にソート*/
     else           {stk[top++].push( flagB,L,l-1); flagB=(!flagB);  L=r+1;} /*右を先にソート*/
   }//goto LOOP;

   //nxt:                   /*スタックが空になったとき終了する*/
   if (top == 0) {
#ifndef base0               /* 64bit JVM では、コピーした配列をソートした方が速いので次行を使用 */
     System.arraycopy(base, 0, base0, 0, Z);
#endif
     return;
   }
   stk[--top].pop();   /*スタックに積んである値を取り出して、処理を繰り返す*/
 }
} // sort メソッドの終了
} // Sqsort クラスの終了