Merge two sorted arrays with O ( 1 ) extra space | Merge ar1 [ ] and ar2 [ ] with O ( 1 ) extra space ; Iterate through all elements of ar2 [ ] starting from the last element ; Find the smallest element greater than ar2 [ i ] . Move all elements one position ahead till the smallest greater element is not found ; If there was a greater element ; Driver program
def merge ( ar1 , ar2 , m , n ) : NEW_LINE INDENT for i in range ( n - 1 , - 1 , - 1 ) : NEW_LINE INDENT last = ar1 [ m - 1 ] NEW_LINE j = m - 2 NEW_LINE while ( j >= 0 and ar1 [ j ] > ar2 [ i ] ) : NEW_LINE INDENT ar1 [ j + 1 ] = ar1 [ j ] NEW_LINE j -= 1 NEW_LINE DEDENT if ( j != m - 2 or last > ar2 [ i ] ) : NEW_LINE INDENT ar1 [ j + 1 ] = ar2 [ i ] NEW_LINE ar2 [ i ] = last NEW_LINE DEDENT DEDENT DEDENT ar1 = [ 1 , 5 , 9 , 10 , 15 , 20 ] NEW_LINE ar2 = [ 2 , 3 , 8 , 13 ] NEW_LINE m = len ( ar1 ) NEW_LINE n = len ( ar2 ) NEW_LINE merge ( ar1 , ar2 , m , n ) NEW_LINE print ( " After Merging First Array : " , ▁ end = " " ) NEW_LINE for i in range ( m ) : NEW_LINE INDENT print ( ar1 [ i ] , " ▁ " , end = " " ) NEW_LINE DEDENT print ( " Second Array : " , ▁ end = " " ) NEW_LINE for i in range ( n ) : NEW_LINE INDENT print ( ar2 [ i ] , " ▁ " , end = " " ) NEW_LINE DEDENT