We have an n x m matrix whose rows are sorted, we need to print the numbers in the matrix in ascending order. The columns are not necessarly sorted. The solution that came to my mind was simple merging the rows in the matrix considering them as separate lists(basically the merging step in merge sort) which in merge sort takes O(n). I wanted to know what is the complexity of merging n separate arrays as in this case. I thought it would be O(n x m) but I am not sure.
Also, what would be a better way to print the numbers in ascending order? merging n lists at one go or merging 2 lists at a time till we consider all rows?
Thanks!
What would be complexity? Its all depends how do you merge N arrays of M size!
Complexity of merging:
- Merging two sorted
M size array goes sequentially. So the complexity of this step is O(2M).
For N rows where each row is sorted and contains Melements.
If do it like (Merging linearly ):
- Merging two rows first--you will get intermediate
2M size sorted array.
- Merge
2M array with another row of N size matix-- you will get 3M size sorted array.
Merging in this manner takes N steps and complexity would be O(N*M).
Better way (divide-and-conquer technique):
Merge all pairs of two consecutive rows first (1,2), (3,4) this give you N/2 pairs of 2M size. in next step merge pairwise. as explain below.
First make pair of two rows and merge all N/2 pairs first and merge them.
e.g pair row(1,2); row(3,4); row(5,6) ......you will get = N/2 pairs each of 2M size.
- Now in next step,
make pair of two merged arrays each of size 2M from previous step and then merge them--you will get N/4 sorted array of 4M size.((merging of 2M with other 2M array -> 4M and complexity is O(2M + 2M) = O(4M))
Progressively Merge all this intermediate sorted arrays util you gets a single sorted array of size N*M. And this time complexity will be M*N*log(N) as total steps required is log(N).
I would like to recommend you to learn merge-sort and its complexity.
