Merging the subarrays using shell sorting Time Complexity : O ( nlog n ) Space Complexity : O ( 1 )
void inPlaceMerge ( int nums [ ] , int start , int end ) { int gap = end - start + 1 ; for ( gap = nextGap ( gap ) ; gap > 0 ; gap = nextGap ( gap ) ) { for ( int i = start ; i + gap <= end ; i ++ ) { int j = i + gap ; if ( nums [ i ] > nums [ j ] ) swap ( nums , i , j ) ; } } }