# Merge k sorted arrays

Hello Everyone,

Given k sorted arrays of size n each, merge them and print the sorted output.

Example:

Input:
k = 3, n = 4
arr[][] = { {1, 3, 5, 7},
{2, 4, 6, 8},
{0, 9, 10, 11}} ;
Output: 0 1 2 3 4 5 6 7 8 9 10 11
Explanation: The output array is a sorted array that contains all the elements of the input matrix.

Input:
k = 3, n = 4
arr[][] = { {1, 5, 6, 8},
{2, 4, 10, 12},
{3, 7, 9, 11},
{13, 14, 15, 16}} ;
Output: 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16
Explanation: The output array is a sorted array that contains all the elements of the input matrix.

Efficient Approach The process might begin with merging arrays into groups of two. After the first merge, we have k/2 arrays. Again merge arrays in groups, now we have k/4 arrays. This is similar to merge sort. Divide k arrays into two halves containing an equal number of arrays until there are two arrays in a group. This is followed by merging the arrays in a bottom-up manner.

• Algorithm:

1. Create a recursive function which takes k arrays and returns the output array.
2. In the recursive function, if the value of k is 1 then return the array else if the value of k is 2 then merge the two arrays in linear time and return the array.
3. If the value of k is greater than 2 then divide the group of k elements into two equal halves and recursively call the function, i.e 0 to k/2 array in one recursive function and k/2 to k array in another recursive function.
4. Print the output array.
• Implementation:

`// C++ program to merge k sorted arrays of size n each.`

`#include<bits/stdc++.h>`

`using` `namespace` `std;`

`#define n 4`

`// Merge arr1[0..n1-1] and arr2[0..n2-1] into`

`// arr3[0..n1+n2-1]`

`void` `mergeArrays(` `int` `arr1[], ` `int` `arr2[], ` `int` `n1,`

` ` `int` `n2, ` `int` `arr3[])`

`{`

` ` `int` `i = 0, j = 0, k = 0;`

` `

` ` `// Traverse both array`

` ` `while` `(i<n1 && j <n2)`

` ` `{`

` ` `// Check if current element of first`

` ` `// array is smaller than current element`

` ` `// of second array. If yes, store first`

` ` `// array element and increment first array`

` ` `// index. Otherwise do same with second array`

` ` `if` `(arr1[i] < arr2[j])`

` ` `arr3[k++] = arr1[i++];`

` ` `else`

` ` `arr3[k++] = arr2[j++];`

` ` `}`

` `

` ` `// Store remaining elements of first array`

` ` `while` `(i < n1)`

` ` `arr3[k++] = arr1[i++];`

` `

` ` `// Store remaining elements of second array`

` ` `while` `(j < n2)`

` ` `arr3[k++] = arr2[j++];`

`}`

`// A utility function to print array elements`

`void` `printArray(` `int` `arr[], ` `int` `size)`

`{`

` ` `for` `(` `int` `i=0; i < size; i++)`

` ` `cout << arr[i] << ` `" "` `;`

`}`

`// This function takes an array of arrays as an argument and`

`// All arrays are assumed to be sorted. It merges them together`

`// and prints the final sorted output.`

`void` `mergeKArrays(` `int` `arr[][n],` `int` `i,` `int` `j, ` `int` `output[])`

`{`

` ` `//if one array is in range`

` ` `if` `(i==j)`

` ` `{`

` ` `for` `(` `int` `p=0; p < n; p++)`

` ` `output[p]=arr[i][p];`

` ` `return` `;`

` ` `}`

` `

` ` `//if only two arrays are left them merge them`

` ` `if` `(j-i==1)`

` ` `{`

` ` `mergeArrays(arr[i],arr[j],n,n,output);`

` ` `return` `;`

` ` `}`

` `

` ` `//output arrays`

` ` `int` `out1[n*(((i+j)/2)-i+1)],out2[n*(j-((i+j)/2))];`

` `

` ` `//divide the array into halves`

` ` `mergeKArrays(arr,i,(i+j)/2,out1);`

` ` `mergeKArrays(arr,(i+j)/2+1,j,out2);`

` `

` ` `//merge the output array`

` ` `mergeArrays(out1,out2,n*(((i+j)/2)-i+1),n*(j-((i+j)/2)),output);`

` `

`}`

` `

` `

`// Driver program to test above functions`

`int` `main()`

`{`

` ` `// Change n at the top to change number of elements`

` ` `// in an array`

` ` `int` `arr[][n] = {{2, 6, 12, 34},`

` ` `{1, 9, 20, 1000},`

` ` `{23, 34, 90, 2000}};`

` ` `int` `k = ` `sizeof` `(arr)/` `sizeof` `(arr[0]);`

` ` `int` `output[n*k];`

` ` `mergeKArrays(arr,0,2, output);`

` `

` ` `cout << ` `"Merged array is "` `<< endl;`

` ` `printArray(output, n*k);`

` `

` ` `return` `0;`

`}`

Output:

Merged array is 1 2 6 9 12 20 23 34 34 90 1000 2000

Complexity Analysis:

• Time Complexity: O( n * k * log k).
There are log k levels as in each level the k arrays are divided in half and at each level the k arrays are traversed. So time Complexity is O( n * k ).
• Space Complexity: O( n * k * log k).
In each level O( n*k ) space is required So Space Complexity is O( n * k * log k).