static void sort(long[] a,int left,int right,long[] work,int workBase,int workLen){
  if (right - left < QUICKSORT_THRESHOLD) {
    sort(a,left,right,true);
    return;
  }
  int[] run=new int[MAX_RUN_COUNT + 1];
  int count=0;
  run[0]=left;
  for (int k=left; k < right; run[count]=k) {
    if (a[k] < a[k + 1]) {
      while (++k <= right && a[k - 1] <= a[k])       ;
    }
 else     if (a[k] > a[k + 1]) {
      while (++k <= right && a[k - 1] >= a[k])       ;
      for (int lo=run[count] - 1, hi=k; ++lo < --hi; ) {
        long t=a[lo];
        a[lo]=a[hi];
        a[hi]=t;
      }
    }
 else {
      for (int m=MAX_RUN_LENGTH; ++k <= right && a[k - 1] == a[k]; ) {
        if (--m == 0) {
          sort(a,left,right,true);
          return;
        }
      }
    }
    if (++count == MAX_RUN_COUNT) {
      sort(a,left,right,true);
      return;
    }
  }
  if (run[count] == right++) {
    run[++count]=right;
  }
 else   if (count == 1) {
    return;
  }
  byte odd=0;
  for (int n=1; (n<<=1) < count; odd^=1)   ;
  long[] b;
  int ao, bo;
  int blen=right - left;
  if (work == null || workLen < blen || workBase + blen > work.length) {
    work=new long[blen];
    workBase=0;
  }
  if (odd == 0) {
    System.arraycopy(a,left,work,workBase,blen);
    b=a;
    bo=0;
    a=work;
    ao=workBase - left;
  }
 else {
    b=work;
    ao=0;
    bo=workBase - left;
  }
  for (int last; count > 1; count=last) {
    for (int k=(last=0) + 2; k <= count; k+=2) {
      int hi=run[k], mi=run[k - 1];
      for (int i=run[k - 2], p=i, q=mi; i < hi; ++i) {
        if (q >= hi || p < mi && a[p + ao] <= a[q + ao]) {
          b[i + bo]=a[p++ + ao];
        }
 else {
          b[i + bo]=a[q++ + ao];
        }
      }
      run[++last]=hi;
    }
    if ((count & 1) != 0) {
      for (int i=right, lo=run[count - 1]; --i >= lo; b[i + bo]=a[i + ao])       ;
      run[++last]=right;
    }
    long[] t=a;
    a=b;
    b=t;
    int o=ao;
    ao=bo;
    bo=o;
  }
}

static void sort ( long [ ] a , int left , int right , long [ ] work , int workBase , int workLen ) { if ( right - left < QUICKSORT_THRESHOLD ) { sort ( a , left , right , true ) ; return ; } int [ ] run = new int [ MAX_RUN_COUNT + 1 ] ; int count = 0 ; run [ 0 ] = left ; for ( int k = left ; k < right ; run [ count ] = k ) { if ( a [ k ] < a [ k + 1 ] ) { while ( ++ k <= right && a [ k - 1 ] <= a [ k ] ) ; } else if ( a [ k ] > a [ k + 1 ] ) { while ( ++ k <= right && a [ k - 1 ] >= a [ k ] ) ; for ( int lo = run [ count ] - 1 , hi = k ; ++ lo < -- hi ; ) { long t = a [ lo ] ; a [ lo ] = a [ hi ] ; a [ hi ] = t ; } } else { for ( int m = MAX_RUN_LENGTH ; ++ k <= right && a [ k - 1 ] == a [ k ] ; ) { if ( -- m == 0 ) { sort ( a , left , right , true ) ; return ; } } } if ( ++ count == MAX_RUN_COUNT ) { sort ( a , left , right , true ) ; return ; } } if ( run [ count ] == right ++ ) { run [ ++ count ] = right ; } else if ( count == 1 ) { return ; } byte odd = 0 ; for ( int n = 1 ; ( n <<= 1 ) < count ; odd ^= 1 ) ; long [ ] b ; int ao , bo ; int blen = right - left ; if ( work == null || workLen < blen || workBase + blen > work . length ) { work = new long [ blen ] ; workBase = 0 ; } if ( odd == 0 ) { System . arraycopy ( a , left , work , workBase , blen ) ; b = a ; bo = 0 ; a = work ; ao = workBase - left ; } else { b = work ; ao = 0 ; bo = workBase - left ; } for ( int last ; count > 1 ; count = last ) { for ( int k = ( last = 0 ) + 2 ; k <= count ; k += 2 ) { int hi = run [ k ] , mi = run [ k - 1 ] ; for ( int i = run [ k - 2 ] , p = i , q = mi ; i < hi ; ++ i ) { if ( q >= hi || p < mi && a [ p + ao ] <= a [ q + ao ] ) { b [ i + bo ] = a [ p ++ + ao ] ; } else { b [ i + bo ] = a [ q ++ + ao ] ; } } run [ ++ last ] = hi ; } if ( ( count & 1 ) != 0 ) { for ( int i = right , lo = run [ count - 1 ] ; -- i >= lo ; b [ i + bo ] = a [ i + ao ] ) ; run [ ++ last ] = right ; } long [ ] t = a ; a = b ; b = t ; int o = ao ; ao = bo ; bo = o ; } }
sorts the specified range of the array using the given workspace array slice if possible for merging
