Yet another thought:

If there are n rows and m columns, you can prove that the time complexity
of any sorting algorithm is Omega(n m) in  the worst case, since, in
the worst case, the algorithm must examine every entry in the matrix.
The O(n m log n) time algorithm I gave you is not much worse than that.

I suspect that a sophisticated method of speeding up row comparison
is not worthwhile, unless you have the right information in advance about
the distributions of the values.  Whether that's possible in your
application, I don't know.