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)
