ŋ߂̃\[ǵANCbN\[gɑă}[W\[g嗬̂悤łB
ő̗ŔuvɂƎv܂BA}[W\[g
@iPjvf̈ړ񐔂
@iQjL[lꍇłxオ\ɂ͖]߂Ȃ
Ȃǂ̌_܂B
#####̂Ƃuv qsort (Sqsort) (r\[g) ܂B
#####ő̓́AL[lɓlꍇɋɂ߂čȂƂłB
SqsortjavaŋLqĂAjavaŋLqTimSort荂łB
GcɂƁASqsort͕⏕z(bas2)ƑΏ۔z(base)
ȉ̂悤ȈړJԂ܂B

```
   bas2:...............    bas2:5555......77787    bas2:..........77787
   base:357358257257237  ` base:332223.........  a  base:3322235555.....
```

vO(150s classt@C 3164byte) ͍ŌɋLڂ܂B
TimSort(900s classt@C 8801byte) 肩ȂRpNgłB
Ԃ𑪒肵̂ȉɋLڂ܂B

```
    \[g   L[̎  @vf@ @JԂ񐔁@(b)
     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:L[̏dȂ@d=100:L[100ށ@d=2:L[jȂ         
      JԂ񐔁FԂ̑덷炷߂Ƀ\[gJԂ   
```

ׂĂ̏ꍇŁASqsort  TimSort 荂łB
ڍׂȑ茋ʁEx`}[NvOETimSort/Sqsort̃\[XR[hȂǂ
@@@@http://ww51.tiki.ne.jp/~srr-cake/qsort/sqs18j/ @@ɂ܂B

uvƂ́AL[lA\[gȌ\[gێ邱ƂłB
uSvƂ́Auӂ̂zɂAُɒԂ𔭐邱ƂłȂv
@@@@@@@ƂƂ܂B

Sqsort ł́uSv邽߂ɁAs{bǧ
(System.nanoTime())ɂ茈肵Ă܂B
ɂAňvZO(n^2)͕ω܂񂪁AX̔m͔ɒႢ̂łB
܂ŒԁACnewlibCuqsort()̎ɂ
ňvZԂւ̔zȂƂA̒ႳĂƎv܂B
AňvZԂ̔m͕ς܂񂪁A
uӂ̂zv邱Ƃ͕s\ɂȂĂƎv܂B


ȏRނ̃\[grƎ̕\̂悤ɂȂ܂B

| @@@@ | TimSort | Sqsort@ | qsort @ |
|:--------|:-------:|:--------:|:--------:|
| @@ |       |         |        |
| Ɨ̈ |       |        |        |
| 萫@ |        |         |    ~     |
| S@ |        |         |    ~     |

܂ATimSortł͔zɓ݂\[gςݕLp܂A
Sqsortɂ̋@\͂܂B
ɁASqsort͓L[l񌻂ꍇɍłB
TimSortɂ̋@\͂܂B
Ȃ킿AʂɃ\[gAj𕪂邽߂Ƀ\[gꍇ
ɂ߂čłB
āAdL[SȂ(j[N)ꍇTimSortQȏ㍂łB

肢F
ňvZԂŚ̖Aɂm̖ƂĈƂĂ܂B
̔zNCbN\[gƂAvf̔r񐔂̕ς C*n*log(n) łB
r񐔂 C*n*log(n)  a{(a=1,2,3...)ȏ ɂȂm P(n,a) 
ǂ̂悤ɕ\΂悢̂ł傤H̕΂B

ȉ Sqsort ̃\[XR[hłB

```
/***************************************************/
/*         Sqsort   (stable qsort)                 */
/*                                                 */
/* by ͑ ms (kawamura tomoyuki)    2021.2.27   */
/*             t-kawa@crux.ocn.ne.jp               */
/***************************************************/

// Sqsort ͈Ȕr\[gBTimSort荂,Ɨ̈2n(TimSortn),S͂قړ
/*
Ώ۔z(base)ƕ⏕z(bas2)(baseƓ傫)pĈȃ\[gsB
ȉ̂悤 `,a 2iKŗvfړBŁu5v̓s{bg(vf)\ĂB

   bas2:...............    bas2:5555......77787    bas2:..........77787
   base:357358257257237  `  base:332223.........  a  base:3322235555.....

ړ`ŁAs{bgƓvfbas2̍[ɏW߁A5菬vfbase̍[ɏW߁A
5傫vfbas2̉E[ɏW߂B̂Ƃ77787͏()̋tɂȂĂB
ړå_5555͂łɃ\[gԂ̈ʒuɎ܂ĂB
aA5555ȊO̗vf́Abaseł͌ɁAbas2ł͋tɕłB
332223{tO(base/bas2)E擪ʒuEʒu}X^bNɕۑB
ȍ~A77787ɑ΂basebas2̈ӖւēJԂB
z񂪒15ȉɂȂΑ}\[g{ĕz̃\[gA
X^bN{tO(base/bas2)E擪ʒuEʒu}oď𑱂B
X^bNɂȂ΃\[gIB
*/
#define C(x,y)  {           x=(y);       }  /* \[gΏ۔z̗vf̃Rs[ɗp */
#define S(x,y)  {T tmp=(x); x=(y); y=tmp;}  /* \[gΏ۔z̗vf̃Xbvɗp */

#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++;} /* zbase,bas2̓Y𑝂₷ */
#define D(x) {x--;} /* zbase,bas2̓Y炷 */

import java.util.Comparator;

class Sqsort {

static int L,R;        // L,ŔAbase܂bas2̃\[gΏۂƂȂ̈[L`R]̍[ƉE[
static boolean flagB;  // [L`R]̈悪baseɂƂtrueAbas2ɂƂfalse
// pop\bh L,R,flagB ֑ł悤ɁAsort\bh̃[Jϐ炱ֈړ

//#define  base0  base  /*LɂƁAzbase0𕡎ʂȂB 32bitJVMł͗L̕*/

@SuppressWarnings({"unchecked"})
public static <T> void sort( T[] base0, Comparator<? super T> cmp ) {//base0:\[gΏۂłz
                                                                     //  cmp:vf̔r֐
 int l,r,m; //ptrB[L`R]Ԃ̗vfptrB[L`l],ptrR[r`R],ptrR[L`m]֐U蕪Bl̈ r̈ m̈
 T[] ptrB, ptrR; //flagB̂Ƃ ptrB==base ptrR==bas2A!flagB̂Ƃ ptrB==bas2 ptrR==baseB
 int n,t,p;      // ńA݃\[g[L`R]̗̈vfBt͍ƗpBpL`RԂړY
 final long rndm = (System.nanoTime() & 0xFFFFFFFFFFFFL); //nanoTime()𗐐ƂĎgp

 class StkElt {             //X^bN[JNXŎ
   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̍ől2^31-1Ȃ̂łRQŏ\
 StkElt stk[] = new StkElt[STK_LEN];
 for (int i=0; i<STK_LEN; i++) stk[i] = new StkElt();
 int top = 0;               // X^bN|C^̏l
   
 int Z = base0.length;      // sort\bhɓnꂽ\[gΏ۔z̗vf
#ifndef base0               /* 64bit JVM ł́ARs[z\[ĝŎsgp */
 T[] base = (T[]) new Object[Z];   System.arraycopy(base0, 0, base, 0, Z);
#endif
 T[] bas2 = (T[]) new Object[Z];  //baseƑ΂ɂȂĎgpBAm̈̃Rs[͏base

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

 //܂ł́Asort̂P̌ĂяoĂPxs

 for(;;) {
   for(;;) {//LOOP:
     if (R<L)  {                                 break;/*goto nxt;*/} //vfȂ
     if (L==R) {{if (!flagB) C(base[L],bas2[L])} break;/*goto nxt;*/} //vfP
     
     n = (R - L + 1);      /*vf n>=2 */

     if (n <= 15) { //}\[g   ʂbaseɍ   n==2ł  u15v͎œꂽl
       if (flagB) { //\[g̈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{       //\[g̈bas2[L`R] t ɂȂĂ
         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;}

     {//R_iRvfs{bgI@̂߂X_QV_̔łj
       int rnd = (int)(rndm % ((n >> 1) - 2)); //nanoTime()𗐐ƂĎgp
       T ll=ptrB[L+rnd], rr=ptrB[R-rnd],       //ӂU𖳌邽߁Avf𗐐őI
         mm=ptrB[L + (n >> 1)]; //̗vf   //R_̓A_Q_ł͈ӂz񂪍Ă܂

       T mmm=med3p(ll,mm,rr);                  //R_rāAmmmɃs{bgZbg

     // l:s{bg菬vf(vf)ɒu  r:vfɒu  m:vfɒu
     // ptrR[L`m]:[m̈  ptrR[r`R]:̉E[r̈(bas2r̈͋tƂȂ)
     // ptrB[L`l]:[l̈  ptrB[L`R]:̑Svf[l̈,r̈,m̈֐U
       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̈ɂ͏ȂƂvfPzu
     assert (l-L)+(m-L)+(R-r)==n;   //l̈,r̈,m̗̈vf̍v ptrB[L`R]̗vfɓ

     if (m-L == 1) {        //m̈basêׂʒuɈړ
       C(base[l],ptrR[L])   //vfP̂Ƃ́APɑî͍߁Bȗ\j
     }else{
       if (flagB) {
         System.arraycopy(bas2, L, base, l, m-L);                 //bas2m̈͏Ɍ
       }else{
         if (m<=l) {
           p=l; do {D(m) C(base[p],base[m]) I(p)} while (L<m);    //basem̈͏ɋt
         }else{
           for (t=m-1, p=l; p<t;) {S(base[p],base[t]) I(p) D(t)}  //m̈Ƃ̈ړ悪dȂƂ
           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;} /*Ƀ\[g*/
     else           {stk[top++].push( flagB,L,l-1); flagB=(!flagB);  L=r+1;} /*EɃ\[g*/
   }//goto LOOP;

   //nxt:                   /*X^bNɂȂƂI*/
   if (top == 0) {
#ifndef base0               /* 64bit JVM ł́ARs[z\[ĝŎsgp */
     System.arraycopy(base, 0, base0, 0, Z);
#endif
     return;
   }
   stk[--top].pop();   /*X^bNɐςłloāAJԂ*/
 }
} // sort \bh̏I
} // Sqsort NX̏I
```
