Merge K sorted arrays of different sizes | ( Divide and Conquer Approach ) | C ++ program to merge K sorted arrays of different arrays ; 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
#include <iostream> NEW_LINE #include <vector> NEW_LINE using namespace std ; vector < int > mergeTwoArrays ( vector < int > l , vector < int > r ) { vector < int > ret ; int l_in = 0 , r_in = 0 ; while ( l_in + r_in < l . size ( ) + r . size ( ) ) { if ( l_in != l . size ( ) && ( r_in == r . size ( ) l [ l_in ] < r [ r_in ] ) ) { ret . push_back ( l [ l_in ] ) ; l_in ++ ; } else { ret . push_back ( r [ r_in ] ) ; r_in ++ ; } } return ret ; } vector < int > mergeArrays ( vector < vector < int > > arr ) { vector < vector < int > > arr_s ; while ( arr . size ( ) != 1 ) { arr_s . clear ( ) ; for ( int i = 0 ; i < arr . size ( ) ; i += 2 ) { if ( i == arr . size ( ) - 1 ) arr_s . push_back ( arr [ i ] ) ; else arr_s . push_back ( mergeTwoArrays ( arr [ i ] , arr [ i + 1 ] ) ) ; } arr = arr_s ; } return arr [ 0 ] ; } int main ( ) { vector < vector < int > > arr { { 3 , 13 } , { 8 , 10 , 11 } , { 9 , 15 } } ; vector < int > output = mergeArrays ( arr ) ; for ( int i = 0 ; i < output . size ( ) ; i ++ ) cout << output [ i ] << " ▁ " ; return 0 ; }