Aim- Given k number of sorted arrays of size n each, our aim is to merge them into a single sorted array.
Naive Approach-
Idea- The approach is to copy all elements of k arrays into a single array and use a sorting algorithm. Hence we will obtain a sorted array.
Note- Here I have directly used the sort function from STL.
Output - 1 2 3 3 4 5 6 12 13 14 15 16 20
Analysis - So, as the size of an array is n. So the total number of elements in the worst case is n*k.
Time - 1. O(n*k) => for copying into a single array
2. O((n*k)*log(n*k)) => for sorting overall array
Overall Time complexity - O((n*k)*log(n*k))
Auxiliary Space complexity- O(n*k)
Efficient Approach-
Observation- We will now try to look at an observation that we completely ignored previously i.e. initially all k-arrays are sorted.
Idea- For now assume that k is 2. Then we can combine 2 arrays efficiently using two pointer techniques which you should be aware of(maintain a pointer for each array now include the minimum of both and increment the pointer of an array of which number is chosen). For two array this can be done in O(n) where n is the maximum size of the array.
Now we make pairs of 2 arrays and compute the resultant array So basically if k arrays then k/2 pairs will be formed and recursively do the same for them as well until we will get only one array being sorted and containing all elements.
Implementation-
1.MergeTwoArray is written specifically to merge two arrays.
2.mergeKArrays is a function that is recursively called until our k reduces to 2 or 1.
Analysis-
1.Time Complexity- Since there are k arrays there will be log(k) levels and corresponding to each level we have to check all the numbers and combine them so,
Time - O(n*k*log(k))
2.Space Complexity- Similarly we have to allocate
O(n*k) space in each level so
Space- O(n*k*log(k))
Prerequisite - knowledge of heap data structure.
The idea is to use min-heap. This method has the same time complexity as the upper method but has a better space complexity. We create a min-heap and add all the first elements of arrays and then extract min from it as the array is sorted this will result in giving minimum element and after extracting we add the next element from the same array from which this element belonged(For this, we have to do some augmentation of heap data structure) and in this manner we will get a sorted array.
Algorithm:
1. Create a min-heap and insert the first element of all k arrays.
2. Run a loop until the size of MinHeap is greater than zero.
3. Extract the top element of the MinHeap and print the element.
4. Now insert the next element from the same array in which the removed element belonged.
5. Hence we will get our result.
Implementation- Basically Augmentation which we will do in a heap so that at the time of extraction we can tell from which array it is extracted and what index to choose now, is to use 3 integers storing value, the position of the corresponding array, index of next element in that array. And we have to use min heap on this data structure So we have to write a comparator function as well. Lets see how we implement it.
1. Time Complexity- Insertion and extraction in mean heap require
O(log(size(heap))).Here size of the heap will always be nearly k.
And we have to add and extract n*k numbers So
Time - O(n*k*log(k)).
2. Space Complexity- O(k) for heap + O(n*k) for final answer
Code-
Note - By the same idea, we can implement a solution for different size array as well.
Important Practice problem-
https://leetcode.com/problems/merge-sorted-array/
https://leetcode.com/problems/merge-two-sorted-lists/
https://leetcode.com/problems/merge-k-sorted-lists/
This article is contributed by Adarsh Agrawal
So that’s it for this article we will be coming up with our next article on further topics of Algorithms very soon till then keep learning, keep coding, keep reading and keep improving !!
Happy Coding
By Programmers Army 😊