public void shuttlesort ( int from [ ] , int to [ ] , int low , int high ) { if ( high - low < 2 ) { return ; } int middle = ( low + high ) / 2 ; shuttlesort ( to , from , low , middle ) ; shuttlesort ( to , from , middle , high ) ; int p = low ; int q = middle ; /* This is an optional short-cut; at each recursive call, check to see if the elements in this subset are already ordered. If so, no further comparisons are needed; the sub-array can just be copied. The array must be copied rather than assigned otherwise sister calls in the recursion might get out of sync. When the number of elements is three they are partitioned so that the first set, [low, mid), has one element and and the second, [mid, high), has two. We skip the optimisation when the number of elements is three or less as the first compare in the normal merge will produce the same sequence of steps. This optimisation seems to be worthwhile for partially ordered lists but some analysis is needed to find out how the performance drops to Nlog(N) as the initial order diminishes - it may drop very quickly. */ if ( high - low >= 4 && compare ( from [ middle - 1 ] , from [ middle ] ) <= 0 ) { System . arraycopy ( from , low , to , low , high - low ) ; return ; } // A normal merge. for ( int i = low ; i < high ; i ++ ) { if ( q >= high || ( p < middle && compare ( from [ p ] , from [ q ] ) <= 0 ) ) { to [ i ] = from [ p ++ ] ; } else { to [ i ] = from [ q ++ ] ; } } }
using it here is that unlike qsort it is stable .