gistfile1.java

private void mergeSortTernary(int l, int r) {
  	 if( l < r ) {
        int p = (r-l)/3;
        int q = 2*p;
        int m1=p+l;
        int m2 = l+q;
        mergeSortTernary(l, m1);
        mergeSortTernary(m1+1, m2);
        mergeSortTernary(m2+1, r);
        mergeTernary(l, m1, m2, r);
      }
    }

    private void mergeTernary(int l, int m1, int m2, int r) {
		  int[] B = new int[r-l+1];
      int i = 0;
      int k = m1+1;
      int k2 = m2+1;
      int j=l;
      while (j<=m1 && k<=m2&& k2<=r) {
        if (A[j] <= A[k]) {
          B[i++] = A[j++];
        } else if (A[k] <= A[k2]) {
          B[i++] = A[k++];
        } else {
          B[i++] = A[k2++];
        }
      }
      while (j<=m1)  {
        B[i++] = A[j++];
      }
      while (k<=m2)  {
        B[i++] = A[k++];
      }
      while (k2<=r) {
        B[i++] = A[k2++];
      }
      for(i = l; i<=r;i++) {
        A[i] = B[i-l];
      }
	}