private static < T extends Comparable < ? super T > > void merge ( T [ ] arr , T [ ] tmpArr , int lPos , int rPos , int rEnd ) { int lEnd = rPos - 1 ; int tPos = lPos ; int leftTmp = lPos ; while ( lPos <= lEnd && rPos <= rEnd ) { if ( arr [ lPos ] . compareTo ( arr [ rPos ] ) <= 0 ) { tmpArr [ tPos ++ ] = arr [ lPos ++ ] ; } else { tmpArr [ tPos ++ ] = arr [ rPos ++ ] ; } } //copy the rest element of the left half subarray. while ( lPos <= lEnd ) { tmpArr [ tPos ++ ] = arr [ lPos ++ ] ; } //copy the rest elements of the right half subarray. (only one loop will be execute) while ( rPos <= rEnd ) { tmpArr [ tPos ++ ] = arr [ rPos ++ ] ; } //copy the tmpArr back cause we need to change the arr array items. for ( ; rEnd >= leftTmp ; rEnd -- ) { arr [ rEnd ] = tmpArr [ rEnd ] ; } }
internal method to merge the sorted halves of a subarray