# Merge sort mxn matrix

The question is as follows:

I am new to this, and I do not understand how to apply divide and conquer to a matrix, the algorithm that I have come up with is as follows (I am not sure if I am correct)

I thought I can divide the matrix into a matrices of 3 x 3 and 2 x 3 first. Then I will apply sorting of rows over column individually on both the matrices. Finally I will copy the second matrix sorting result over to the first sorted matrix. However, my problem is how do I sort the matrix first in to some order so that my division will yield a correct partition else what happens is, post copy I have to again sort (Which I thought is probably wrong)

• Please transcribe the text in your image -- images are inaccessible to search engines and people with visual difficulties. – David Richerby Sep 8 '18 at 18:51

As far as I can see, "sort the rows of the matrix, with respect to their columns" means that you're supposed to sort the rows lexicographically. That is, the row $$a_1\ a_2\ \ldots\ a_n$$ comes before $$b_1\ b_2\ \ldots\ b_n$$ if and only if there's some $i$ such that $a_j=b_j$ for $j<i$ and $a_i<b_i$.
• Check each possible $i$ in turn. – David Richerby Sep 8 '18 at 19:10