private void trSort ( int ISA , int n , int depth ) { TRBudget budget = new TRBudget ( trIlg ( n ) * 2 / 3 , n ) ; int ISAd ; int first , last ; // SA pointers int t , skip , unsorted ; for ( ISAd = ISA + depth ; - n < SA [ 0 ] ; ISAd += ISAd - ISA ) { first = 0 ; skip = 0 ; unsorted = 0 ; do { if ( ( t = SA [ first ] ) < 0 ) { first -= t ; skip += t ; } else { if ( skip != 0 ) { SA [ first + skip ] = skip ; skip = 0 ; } last = SA [ ISA + t ] + 1 ; if ( 1 < ( last - first ) ) { budget . count = 0 ; trIntroSort ( ISA , ISAd , first , last , budget ) ; if ( budget . count != 0 ) { unsorted += budget . count ; } else { skip = first - last ; } } else if ( ( last - first ) == 1 ) { skip = - 1 ; } first = last ; } } while ( first < n ) ; if ( skip != 0 ) { SA [ first + skip ] = skip ; } if ( unsorted == 0 ) { break ; } } }
Tandem repeat sort