Merge K sorted arrays | Set 3 ( Using Divide and Conquer Approach ) | Python3 program to merge K sorted arrays ; Function to perform merge operation ; to store the starting point of left and right array ; to store the size of left and right array ; array to temporarily store left and right array ; storing data in left array ; storing data in right array ; to store the current index of temporary left and right array ; to store the current index for output array ; two pointer merge for two sorted arrays ; Code to drive merge - sort and create recursion tree ; base step to initialize the output array before performing merge operation ; to sort left half ; to sort right half ; merge the left and right half ; Driver code ; input 2D - array ; Number of arrays ; Output array ; Print merged array
n = 4 ; NEW_LINE def merge ( l , r , output ) : NEW_LINE INDENT l_in = l * n ; NEW_LINE r_in = ( ( l + r ) // 2 + 1 ) * n ; NEW_LINE l_c = ( ( l + r ) // 2 - l + 1 ) * n ; NEW_LINE r_c = ( r - ( l + r ) // 2 ) * n ; NEW_LINE l_arr = [ 0 ] * l_c ; r_arr = [ 0 ] * r_c ; NEW_LINE for i in range ( l_c ) : NEW_LINE INDENT l_arr [ i ] = output [ l_in + i ] ; NEW_LINE DEDENT for i in range ( r_c ) : NEW_LINE INDENT r_arr [ i ] = output [ r_in + i ] ; NEW_LINE DEDENT l_curr = 0 ; r_curr = 0 ; NEW_LINE in1 = l_in ; NEW_LINE while ( l_curr + r_curr < l_c + r_c ) : NEW_LINE INDENT if ( r_curr == r_c or ( l_curr != l_c and l_arr [ l_curr ] < r_arr [ r_curr ] ) ) : NEW_LINE INDENT output [ in1 ] = l_arr [ l_curr ] ; NEW_LINE l_curr += 1 ; in1 += 1 ; NEW_LINE DEDENT else : NEW_LINE INDENT output [ in1 ] = r_arr [ r_curr ] ; NEW_LINE r_curr += 1 ; in1 += 1 ; NEW_LINE DEDENT DEDENT DEDENT def divide ( l , r , output , arr ) : NEW_LINE INDENT if ( l == r ) : NEW_LINE INDENT for i in range ( n ) : NEW_LINE INDENT output [ l * n + i ] = arr [ l ] [ i ] ; NEW_LINE DEDENT return ; NEW_LINE DEDENT divide ( l , ( l + r ) // 2 , output , arr ) ; NEW_LINE divide ( ( l + r ) // 2 + 1 , r , output , arr ) ; NEW_LINE merge ( l , r , output ) ; NEW_LINE DEDENT if __name__ == " _ _ main _ _ " : NEW_LINE INDENT arr = [ [ 5 , 7 , 15 , 18 ] , [ 1 , 8 , 9 , 17 ] , [ 1 , 4 , 7 , 7 ] ] ; NEW_LINE k = len ( arr ) ; NEW_LINE output = [ 0 ] * ( n * k ) ; NEW_LINE divide ( 0 , k - 1 , output , arr ) ; NEW_LINE for i in range ( n * k ) : NEW_LINE INDENT print ( output [ i ] , end = " ▁ " ) ; NEW_LINE DEDENT DEDENT