Merge two sorted arrays in O ( 1 ) extra space using Heap | Function to perform min heapify on array brr [ ] ; Stores index of left child of i . ; Stores index of right child of i . ; Stores index of the smallest element in ( arr [ i ] , arr [ left ] , arr [ right ] ) ; Check if arr [ left ] less than arr [ smallest ] ; Update smallest ; Check if arr [ right ] less than arr [ smallest ] ; Update smallest ; If i is not the index of smallest element ; Swap arr [ i ] and arr [ smallest ] ; Perform heapify on smallest ; Function to merge two sorted arrays ; Traverse the array arr [ ] ; Check if current element is less than brr [ 0 ] ; Swap arr [ i ] and brr [ 0 ] ; Perform heapify on brr [ ] ; Sort array brr [ ] ; Function to print array elements ; Traverse array arr [ ] ; Driver code ; Function call to merge two array ; Print first array ; Print Second array .
def minHeapify ( brr , i , M ) : NEW_LINE INDENT left = 2 * i + 1 NEW_LINE right = 2 * i + 2 NEW_LINE smallest = i NEW_LINE if ( left < M and brr [ left ] < brr [ smallest ] ) : NEW_LINE INDENT smallest = left NEW_LINE DEDENT if ( right < M and brr [ right ] < brr [ smallest ] ) : NEW_LINE INDENT smallest = right NEW_LINE DEDENT if ( smallest != i ) : NEW_LINE INDENT brr [ i ] , brr [ smallest ] = brr [ smallest ] , brr [ i ] NEW_LINE minHeapify ( brr , smallest , M ) NEW_LINE DEDENT DEDENT def merge ( arr , brr , N , M ) : NEW_LINE INDENT for i in range ( N ) : NEW_LINE INDENT if ( arr [ i ] > brr [ 0 ] ) : NEW_LINE INDENT arr [ i ] , brr [ 0 ] = brr [ 0 ] , arr [ i ] NEW_LINE minHeapify ( brr , 0 , M ) NEW_LINE DEDENT DEDENT brr . sort ( ) NEW_LINE DEDENT def printArray ( arr , N ) : NEW_LINE INDENT for i in range ( N ) : NEW_LINE INDENT print ( arr [ i ] , end = " ▁ " ) NEW_LINE DEDENT DEDENT if __name__ == ' _ _ main _ _ ' : NEW_LINE INDENT arr = [ 2 , 23 , 35 , 235 , 2335 ] NEW_LINE brr = [ 3 , 5 ] NEW_LINE N = len ( arr ) NEW_LINE M = len ( brr ) NEW_LINE merge ( arr , brr , N , M ) NEW_LINE printArray ( arr , N ) NEW_LINE printArray ( brr , M ) NEW_LINE DEDENT