Efficiently merging two sorted arrays with O ( 1 ) extra space | Function to find next gap . ; comparing elements in the first array . ; comparing elements in both arrays . ; comparing elements in the second array . ; Driver code ; Function Call
def nextGap ( gap ) : NEW_LINE INDENT if ( gap <= 1 ) : NEW_LINE INDENT return 0 NEW_LINE DEDENT return ( gap // 2 ) + ( gap % 2 ) NEW_LINE DEDENT def merge ( arr1 , arr2 , n , m ) : NEW_LINE INDENT gap = n + m NEW_LINE gap = nextGap ( gap ) NEW_LINE while gap > 0 : NEW_LINE INDENT i = 0 NEW_LINE while i + gap < n : NEW_LINE INDENT if ( arr1 [ i ] > arr1 [ i + gap ] ) : NEW_LINE INDENT arr1 [ i ] , arr1 [ i + gap ] = arr1 [ i + gap ] , arr1 [ i ] NEW_LINE DEDENT i += 1 NEW_LINE DEDENT j = gap - n if gap > n else 0 NEW_LINE while i < n and j < m : NEW_LINE INDENT if ( arr1 [ i ] > arr2 [ j ] ) : NEW_LINE INDENT arr1 [ i ] , arr2 [ j ] = arr2 [ j ] , arr1 [ i ] NEW_LINE DEDENT i += 1 NEW_LINE j += 1 NEW_LINE DEDENT if ( j < m ) : NEW_LINE INDENT j = 0 NEW_LINE while j + gap < m : NEW_LINE INDENT if ( arr2 [ j ] > arr2 [ j + gap ] ) : NEW_LINE INDENT arr2 [ j ] , arr2 [ j + gap ] = arr2 [ j + gap ] , arr2 [ j ] NEW_LINE DEDENT j += 1 NEW_LINE DEDENT DEDENT gap = nextGap ( gap ) NEW_LINE DEDENT DEDENT if __name__ == " _ _ main _ _ " : NEW_LINE INDENT a1 = [ 10 , 27 , 38 , 43 , 82 ] NEW_LINE a2 = [ 3 , 9 ] NEW_LINE n = len ( a1 ) NEW_LINE m = len ( a2 ) NEW_LINE merge ( a1 , a2 , n , m ) NEW_LINE print ( " First ▁ Array : ▁ " , end = " " ) NEW_LINE for i in range ( n ) : NEW_LINE INDENT print ( a1 [ i ] , end = " ▁ " ) NEW_LINE DEDENT print ( ) NEW_LINE print ( " Second ▁ Array : ▁ " , end = " " ) NEW_LINE for i in range ( m ) : NEW_LINE INDENT print ( a2 [ i ] , end = " ▁ " ) NEW_LINE DEDENT print ( ) NEW_LINE DEDENT