Sorting rectangular matrices

Retina, 8 6 5 bytes

Thanks to randomra for saving 3 bytes.

O#`.+

Input format is a bit awkward. Both the delimiter within rows and between rows needs to consist of line-terminating characters (i.e. those not matched by .). E.g. you could use single linefeeds within rows and double linefeeds between rows. Output is printed in the same format.

Try it online!

Explanation

The perfect challenge to show off Retina's latest addition: sort stages!

Sort stages work as follows: the regex is matched against the entire string. The matches are then the things that are being sorted, whereas everything around them is treated as "list delimiters" and left unchanged. This challenge can be solved if we treat the input as a flat list, sort that and reshape it into the original matrix form. That's exactly how sort stages work, except there are no explicit steps for flattening and reshaping - Retina just ignores the 2D structure altogether.

As for this code in particular, the regex is .+ which simply matches all runs of non-linefeed characters, which is all the numbers due to the input format. By default, the matches are sorted lexicographically, but the # option tells Retina to sort them numerically (by the first signed integer that appears in the match).

For three additional bytes, this could support any input format whatsoever, by using the regex -?\d+.

Pyth, 6 5 bytes

1 byte thanks to DenkerAffe

cSsQE

Demonstration

Input is the matrix, followed by its width.

To sort the matrix, I simply flatten it into a list, sort the list, and chop it into a matrix again. Since every subsequence of a sorted list is sorted, this results in a sorted matrix.

Python, 43 bytes

lambda M:eval("map(sorted,zip(*"*2+"M))))")

The interesting question is how to apply mapsort-transpose twice. The shortest I found was to eval a string that has it twice. Compare some alternatives:

lambda M:eval("map(sorted,zip(*"*2+"M))))")
lambda M:map(sorted,zip(*map(sorted,zip(*M))))
s="map(sorted,zip(*%s))";lambda M:eval(s%s%M)
g=lambda M:map(sorted,zip(*M));lambda M:g(g(M))
f=lambda M,n=-1:n*M or f(map(sorted,zip(*M)),n+1)
def f(M):exec"M=map(sorted,zip(*M));"*2;return M

(The second and fourth can be shortened by 1 byte by aliasing sorted, but it's not enough.)

An alternative approach of converting to 1D, sorting, and reshaping to 2D, is very close, at 44 bytes. The width w is taken as an input.

lambda M,w:zip(*[iter(sorted(sum(M,[])))]*w)