Naive Approach for Merging k sorted arrays
Create an output array of size (N * K) and then copy all the elements into the output array followed by sorting.
Follow the given steps to solve the problem:
- Create an output array of size N * K.
- Traverse the matrix from start to end and insert all the elements in the output array.
- Sort and print the output array.
Below is the implementation of the above approach:
C++14
// C++ program to merge K sorted arrays of size n each. #include <bits/stdc++.h> using namespace std; #define N 4 // 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 a, int output[]) { int c = 0; // traverse the matrix for (int i = 0; i < a; i++) { for (int j = 0; j < N; j++) output = arr[i][j]; } // sort the array sort(output, output + N * a); } // Driver's code 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]; // Function call mergeKArrays(arr, 3, output); cout << "Merged array is " << endl; printArray(output, N * K); return 0; } |
Java
// Java program to merge K sorted arrays of size N each. import java.io.*; import java.util.*; class GFG { // 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. public static void mergeKArrays(int[][] arr, int a, int[] output) { int c = 0; // traverse the matrix for (int i = 0; i < a; i++) { for (int j = 0; j < 4; j++) output = arr[i][j]; } // sort the array Arrays.sort(output); } // A utility function to print array elements public static void printArray(int[] arr, int size) { for (int i = 0; i < size; i++) System.out.print(arr[i] + " "); } // Driver's code public static void main(String[] args) { int[][] arr = { { 2, 6, 12, 34 }, { 1, 9, 20, 1000 }, { 23, 34, 90, 2000 } }; int K = 4; int N = 3; int[] output = new int[N * K]; // Function call mergeKArrays(arr, N, output); System.out.println("Merged array is "); printArray(output, N * K); } } |
Python3
# Python3 program to merge k sorted arrays of size n each. # 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. def mergeKArrays(arr, a, output): c = 0 # traverse the matrix for i in range(a): for j in range(4): output = arr[i][j] c += 1 # sort the array output.sort() # A utility function to print array elements def printArray(arr, size): for i in range(size): print(arr[i], end=" ") # Driver's code if __name__ == '__main__': arr = [[2, 6, 12, 34], [1, 9, 20, 1000], [23, 34, 90, 2000]] K = 4 N = 3 output = [0 for i in range(N * K)] # Function call mergeKArrays(arr, N, output) print("Merged array is ") printArray(output, N * K) # This code is contributed by umadevi9616 |
C#
// C# program to merge K sorted arrays of size n each. using System; public class GFG { // 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 readonly sorted output. public static void mergeKArrays(int[, ] arr, int a, int[] output) { int c = 0; // traverse the matrix for (int i = 0; i < a; i++) { for (int j = 0; j < 4; j++) output = arr[i, j]; } // sort the array Array.Sort(output); } // A utility function to print array elements public static void printArray(int[] arr, int size) { for (int i = 0; i < size; i++) Console.Write(arr[i] + " "); } // Driver's code public static void Main(String[] args) { int[, ] arr = { { 2, 6, 12, 34 }, { 1, 9, 20, 1000 }, { 23, 34, 90, 2000 } }; int K = 4; int N = 3; int[] output = new int[N * K]; // Function call mergeKArrays(arr, N, output); Console.WriteLine("Merged array is "); printArray(output, N * K); } } // This code is contributed by Rajput-Ji |
Javascript
// Javascript program to merge k sorted // arrays of size n each. // 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. function mergeKArrays(arr , a, output) { var c = 0; // traverse the matrix for (i = 0; i < a; i++) { for (j = 0; j < 4; j++) output = arr[i][j]; } // sort the array output.sort((a,b)=>a-b); } // A utility function to print array elements function printArray(arr , size) { for (i = 0; i < size; i++) document.write(arr[i] + " "); } // Driver program to test above functions var arr = [ [ 2, 6, 12, 34 ], [ 1, 9, 20, 1000 ], [ 23, 34, 90, 2000 ] ]; var K = 4; var N = 3; var output = Array(N * K).fill(0); mergeKArrays(arr, N, output); document.write("Merged array is "); printArray(output, N * K); // This code contributed by Rajput-Ji |
Output
Merged array is 1 2 6 9 12 20 23 34 34 90 1000 2000
Time Complexity: O(N * K * log (N*K)), Since the resulting array is of size N*K.
Space Complexity: O(N * K), The output array is of size N * K.
Merge k sorted arrays | Set 1
Given K sorted arrays of size N each, merge them and print the sorted output.
Examples:
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 = 4, 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.