Merge two sorted arrays in O ( 1 ) extra space using QuickSort partition | Function to perform the partition around the pivot element ; Stores index of each element of the array , arr [ ] ; Stores index of each element of the array , brr [ ] ; Traverse both the array ; If pivot is smaller than arr [ l ] ; If Pivot is greater than brr [ r ] ; If either arr [ l ] > Pivot or brr [ r ] < Pivot ; Function to merge the two sorted array ; Stores index of each element of the array arr [ ] ; Stores index of each element of the array brr [ ] ; Stores index of each element the final sorted array ; Stores the pivot element ; Traverse both the array ; If pivot element is not found or index < N ; If pivot element is not found or index < N ; Place the first N elements of the sorted array into arr [ ] and the last M elements of the sorted array into brr [ ] ; Sort both the arrays ; Print the first N elements in sorted order ; Print the last M elements in sorted order ; Driver Code
def partition ( arr , N , brr , M , Pivot ) : NEW_LINE INDENT l = N - 1 NEW_LINE r = 0 NEW_LINE while ( l >= 0 and r < M ) : NEW_LINE INDENT if ( arr [ l ] < Pivot ) : NEW_LINE INDENT l -= 1 NEW_LINE DEDENT elif ( brr [ r ] > Pivot ) : NEW_LINE INDENT r += 1 NEW_LINE DEDENT else : NEW_LINE INDENT arr [ l ] , brr [ r ] = brr [ r ] , arr [ l ] NEW_LINE l -= 1 NEW_LINE r += 1 NEW_LINE DEDENT DEDENT DEDENT def Merge ( arr , N , brr , M ) : NEW_LINE INDENT l = 0 NEW_LINE r = 0 NEW_LINE index = - 1 NEW_LINE Pivot = 0 NEW_LINE while ( index < N and l < N and r < M ) : NEW_LINE INDENT if ( arr [ l ] < brr [ r ] ) : NEW_LINE INDENT Pivot = arr [ l ] NEW_LINE l += 1 NEW_LINE DEDENT else : NEW_LINE INDENT Pivot = brr [ r ] NEW_LINE r += 1 NEW_LINE DEDENT index += 1 NEW_LINE DEDENT while ( index < N and l < N ) : NEW_LINE INDENT Pivot = arr [ l ] NEW_LINE l += 1 NEW_LINE index += 1 NEW_LINE DEDENT while ( index < N and r < M ) : NEW_LINE INDENT Pivot = brr [ r ] NEW_LINE r += 1 NEW_LINE index += 1 NEW_LINE DEDENT partition ( arr , N , brr , M , Pivot ) NEW_LINE arr = sorted ( arr ) NEW_LINE brr = sorted ( brr ) NEW_LINE for i in range ( N ) : NEW_LINE INDENT print ( arr [ i ] , end = " ▁ " ) NEW_LINE DEDENT for i in range ( M ) : NEW_LINE INDENT print ( brr [ i ] , end = " ▁ " ) NEW_LINE DEDENT DEDENT if __name__ == ' _ _ main _ _ ' : NEW_LINE INDENT arr = [ 1 , 5 , 9 ] NEW_LINE brr = [ 2 , 4 , 7 , 10 ] NEW_LINE N = len ( arr ) NEW_LINE M = len ( brr ) NEW_LINE Merge ( arr , N , brr , M ) NEW_LINE DEDENT