private void ssMergeBackward(int PA, int first, int middle, int last, int buf,
                                 int depth) {
        // PA, first, middle, last, buf are pointers in SA
        int p1, p2;// pointers in SA
        int a, b, c, bufend;// pointers in SA
        int t, r, x;

        bufend = buf + (last - middle) - 1;
        ssBlockSwap(buf, middle, last - middle);

        x = 0;
        if (SA[bufend] < 0) {
            p1 = PA + ~SA[bufend];
            x |= 1;
        } else {
            p1 = PA + SA[bufend];
        }
        if (SA[middle - 1] < 0) {
            p2 = PA + ~SA[middle - 1];
            x |= 2;
        } else {
            p2 = PA + SA[middle - 1];
        }
        for (t = SA[a = last - 1], b = bufend, c = middle - 1; ; ) {
            r = ssCompare(p1, p2, depth);
            if (0 < r) {
                if ((x & 1) != 0) {
                    do {
                        SA[a--] = SA[b];
                        SA[b--] = SA[a];
                    }
                    while (SA[b] < 0);
                    x ^= 1;
                }
                SA[a--] = SA[b];
                if (b <= buf) {
                    SA[buf] = t;
                    break;
                }
                SA[b--] = SA[a];
                if (SA[b] < 0) {
                    p1 = PA + ~SA[b];
                    x |= 1;
                } else {
                    p1 = PA + SA[b];
                }
            } else if (r < 0) {
                if ((x & 2) != 0) {
                    do {
                        SA[a--] = SA[c];
                        SA[c--] = SA[a];
                    }
                    while (SA[c] < 0);
                    x ^= 2;
                }
                SA[a--] = SA[c];
                SA[c--] = SA[a];
                if (c < first) {
                    while (buf < b) {
                        SA[a--] = SA[b];
                        SA[b--] = SA[a];
                    }
                    SA[a] = SA[b];
                    SA[b] = t;
                    break;
                }
                if (SA[c] < 0) {
                    p2 = PA + ~SA[c];
                    x |= 2;
                } else {
                    p2 = PA + SA[c];
                }
            } else {
                if ((x & 1) != 0) {
                    do {
                        SA[a--] = SA[b];
                        SA[b--] = SA[a];
                    }
                    while (SA[b] < 0);
                    x ^= 1;
                }
                SA[a--] = ~SA[b];
                if (b <= buf) {
                    SA[buf] = t;
                    break;
                }
                SA[b--] = SA[a];
                if ((x & 2) != 0) {
                    do {
                        SA[a--] = SA[c];
                        SA[c--] = SA[a];
                    }
                    while (SA[c] < 0);
                    x ^= 2;
                }
                SA[a--] = SA[c];
                SA[c--] = SA[a];
                if (c < first) {
                    while (buf < b) {
                        SA[a--] = SA[b];
                        SA[b--] = SA[a];
                    }
                    SA[a] = SA[b];
                    SA[b] = t;
                    break;
                }
                if (SA[b] < 0) {
                    p1 = PA + ~SA[b];
                    x |= 1;
                } else {
                    p1 = PA + SA[b];
                }
                if (SA[c] < 0) {
                    p2 = PA + ~SA[c];
                    x |= 2;
                } else {
                    p2 = PA + SA[c];
                }
            }
        }
    }
private void ssMergeBackward ( int PA , int first , int middle , int last , int buf , int depth ) { int p1 , p2 ; int a , b , c , bufend ; int t , r , x ; bufend = buf + ( last - middle ) - 1 ; ssBlockSwap ( buf , middle , last - middle ) ; x = 0 ; if ( SA [ bufend ] < 0 ) { p1 = PA + ~ SA [ bufend ] ; x |= 1 ; } else { p1 = PA + SA [ bufend ] ; } if ( SA [ middle - 1 ] < 0 ) { p2 = PA + ~ SA [ middle - 1 ] ; x |= 2 ; } else { p2 = PA + SA [ middle - 1 ] ; } for ( t = SA [ a = last - 1 ] , b = bufend , c = middle - 1 ; ; ) { r = ssCompare ( p1 , p2 , depth ) ; if ( 0 < r ) { if ( ( x & 1 ) != 0 ) { do { SA [ a -- ] = SA [ b ] ; SA [ b -- ] = SA [ a ] ; } while ( SA [ b ] < 0 ) ; x ^= 1 ; } SA [ a -- ] = SA [ b ] ; if ( b <= buf ) { SA [ buf ] = t ; break ; } SA [ b -- ] = SA [ a ] ; if ( SA [ b ] < 0 ) { p1 = PA + ~ SA [ b ] ; x |= 1 ; } else { p1 = PA + SA [ b ] ; } } else if ( r < 0 ) { if ( ( x & 2 ) != 0 ) { do { SA [ a -- ] = SA [ c ] ; SA [ c -- ] = SA [ a ] ; } while ( SA [ c ] < 0 ) ; x ^= 2 ; } SA [ a -- ] = SA [ c ] ; SA [ c -- ] = SA [ a ] ; if ( c < first ) { while ( buf < b ) { SA [ a -- ] = SA [ b ] ; SA [ b -- ] = SA [ a ] ; } SA [ a ] = SA [ b ] ; SA [ b ] = t ; break ; } if ( SA [ c ] < 0 ) { p2 = PA + ~ SA [ c ] ; x |= 2 ; } else { p2 = PA + SA [ c ] ; } } else { if ( ( x & 1 ) != 0 ) { do { SA [ a -- ] = SA [ b ] ; SA [ b -- ] = SA [ a ] ; } while ( SA [ b ] < 0 ) ; x ^= 1 ; } SA [ a -- ] = ~ SA [ b ] ; if ( b <= buf ) { SA [ buf ] = t ; break ; } SA [ b -- ] = SA [ a ] ; if ( ( x & 2 ) != 0 ) { do { SA [ a -- ] = SA [ c ] ; SA [ c -- ] = SA [ a ] ; } while ( SA [ c ] < 0 ) ; x ^= 2 ; } SA [ a -- ] = SA [ c ] ; SA [ c -- ] = SA [ a ] ; if ( c < first ) { while ( buf < b ) { SA [ a -- ] = SA [ b ] ; SA [ b -- ] = SA [ a ] ; } SA [ a ] = SA [ b ] ; SA [ b ] = t ; break ; } if ( SA [ b ] < 0 ) { p1 = PA + ~ SA [ b ] ; x |= 1 ; } else { p1 = PA + SA [ b ] ; } if ( SA [ c ] < 0 ) { p2 = PA + ~ SA [ c ] ; x |= 2 ; } else { p2 = PA + SA [ c ] ; } } } }
Merge-backward with internal buffer.