private static void stableStringSort(String[] arr,String[] src,String[] dst,int start,int end,int chId){
  int length=end - start;
  if (length < SIMPLE_LENGTH) {
    if (src == arr) {
      for (int i=start + 1; i < end; i++) {
        String current=arr[i];
        String prev=arr[i - 1];
        if (current.compareTo(prev) < 0) {
          int j=i;
          do {
            arr[j--]=prev;
          }
 while (j > start && current.compareTo(prev=arr[j - 1]) < 0);
          arr[j]=current;
        }
      }
    }
 else {
      int actualEnd=end - 1;
      dst[start]=src[actualEnd--];
      for (int i=start + 1; i < end; i++, actualEnd--) {
        String current=src[actualEnd];
        String prev;
        int j=i;
        while (j > start && current.compareTo(prev=dst[j - 1]) < 0) {
          dst[j--]=prev;
        }
        dst[j]=current;
      }
    }
    return;
  }
  int s;
  int mid=start + length / 2;
  int lo=start;
  int hi=end - 1;
  if (length > 40) {
    s=length / 8;
    lo=medChar(lo,lo + s,lo + s * 2,src,chId);
    mid=medChar(mid - s,mid,mid + s,src,chId);
    hi=medChar(hi,hi - s,hi - s * 2,src,chId);
  }
  mid=medChar(lo,mid,hi,src,chId);
  int midVal=charAt(src[mid],chId);
  int a, b, c;
  a=b=start;
  c=end - 1;
  int cmp;
  for (int i=start; i < end; i++) {
    String el=src[i];
    cmp=charAt(el,chId) - midVal;
    if (cmp < 0) {
      src[a]=el;
      a++;
    }
 else     if (cmp > 0) {
      dst[c]=el;
      c--;
    }
 else {
      dst[b]=el;
      b++;
    }
  }
  s=b - start;
  if (s > 0) {
    if (arr == src) {
      System.arraycopy(dst,start,arr,a,s);
    }
 else {
      copySwap(dst,start,arr,a,s);
    }
    if (b >= end && midVal == -1) {
      return;
    }
    stableStringSort(arr,arr,arr == dst ? src : dst,a,a + s,chId + 1);
  }
  s=a - start;
  if (s > 0) {
    stableStringSort(arr,src,dst,start,a,chId);
  }
  c++;
  s=end - c;
  if (s > 0) {
    stableStringSort(arr,dst,src,c,end,chId);
  }
}

private static void stableStringSort ( String [ ] arr , String [ ] src , String [ ] dst , int start , int end , int chId ) { int length = end - start ; if ( length < SIMPLE_LENGTH ) { if ( src == arr ) { for ( int i = start + 1 ; i < end ; i ++ ) { String current = arr [ i ] ; String prev = arr [ i - 1 ] ; if ( current . compareTo ( prev ) < 0 ) { int j = i ; do { arr [ j -- ] = prev ; } while ( j > start && current . compareTo ( prev = arr [ j - 1 ] ) < 0 ) ; arr [ j ] = current ; } } } else { int actualEnd = end - 1 ; dst [ start ] = src [ actualEnd -- ] ; for ( int i = start + 1 ; i < end ; i ++ , actualEnd -- ) { String current = src [ actualEnd ] ; String prev ; int j = i ; while ( j > start && current . compareTo ( prev = dst [ j - 1 ] ) < 0 ) { dst [ j -- ] = prev ; } dst [ j ] = current ; } } return ; } int s ; int mid = start + length / 2 ; int lo = start ; int hi = end - 1 ; if ( length > 40 ) { s = length / 8 ; lo = medChar ( lo , lo + s , lo + s * 2 , src , chId ) ; mid = medChar ( mid - s , mid , mid + s , src , chId ) ; hi = medChar ( hi , hi - s , hi - s * 2 , src , chId ) ; } mid = medChar ( lo , mid , hi , src , chId ) ; int midVal = charAt ( src [ mid ] , chId ) ; int a , b , c ; a = b = start ; c = end - 1 ; int cmp ; for ( int i = start ; i < end ; i ++ ) { String el = src [ i ] ; cmp = charAt ( el , chId ) - midVal ; if ( cmp < 0 ) { src [ a ] = el ; a ++ ; } else if ( cmp > 0 ) { dst [ c ] = el ; c -- ; } else { dst [ b ] = el ; b ++ ; } } s = b - start ; if ( s > 0 ) { if ( arr == src ) { System . arraycopy ( dst , start , arr , a , s ) ; } else { copySwap ( dst , start , arr , a , s ) ; } if ( b >= end && midVal == - 1 ) { return ; } stableStringSort ( arr , arr , arr == dst ? src : dst , a , a + s , chId + 1 ) ; } s = a - start ; if ( s > 0 ) { stableStringSort ( arr , src , dst , start , a , chId ) ; } c ++ ; s = end - c ; if ( s > 0 ) { stableStringSort ( arr , dst , src , c , end , chId ) ; } }
performs a sort on the given string array . elements will be re - ordered into ascending order . uses a stable ternary quick sort algorithm .
