Merge K sorted arrays of different sizes | ( Divide and Conquer Approach ) | Function to merge two arrays ; array to store the result after merging l and r ; variables to store the current pointers for l and r ; loop to merge l and r using two pointer ; Function to merge all the arrays ; 2D - array to store the results of a step temporarily ; Loop to make pairs of arrays and merge them ; To clear the data of previous steps ; Returning the required output array ; Driver Code ; Input arrays ; Merged sorted array
def mergeTwoArrays ( l , r ) : NEW_LINE INDENT ret = [ ] NEW_LINE l_in , r_in = 0 , 0 NEW_LINE while l_in + r_in < len ( l ) + len ( r ) : NEW_LINE INDENT if ( l_in != len ( l ) and ( r_in == len ( r ) or l [ l_in ] < r [ r_in ] ) ) : NEW_LINE INDENT ret . append ( l [ l_in ] ) NEW_LINE l_in += 1 NEW_LINE DEDENT else : NEW_LINE INDENT ret . append ( r [ r_in ] ) NEW_LINE r_in += 1 NEW_LINE DEDENT DEDENT return ret NEW_LINE DEDENT def mergeArrays ( arr ) : NEW_LINE INDENT arr_s = [ ] NEW_LINE while len ( arr ) != 1 : NEW_LINE INDENT arr_s [ : ] = [ ] NEW_LINE for i in range ( 0 , len ( arr ) , 2 ) : NEW_LINE INDENT if i == len ( arr ) - 1 : NEW_LINE INDENT arr_s . append ( arr [ i ] ) NEW_LINE DEDENT else : NEW_LINE INDENT arr_s . append ( mergeTwoArrays ( arr [ i ] , arr [ i + 1 ] ) ) NEW_LINE DEDENT DEDENT arr = arr_s [ : ] NEW_LINE DEDENT return arr [ 0 ] NEW_LINE DEDENT if __name__ == " _ _ main _ _ " : NEW_LINE INDENT arr = [ [ 3 , 13 ] , [ 8 , 10 , 11 ] , [ 9 , 15 ] ] NEW_LINE output = mergeArrays ( arr ) NEW_LINE for i in range ( 0 , len ( output ) ) : NEW_LINE INDENT print ( output [ i ] , end = " ▁ " ) NEW_LINE DEDENT DEDENT