One day at work, me and one of my colleagues had a discussion about Microsoft interview questions, I don't remember exactly the whole conversation but I remember I asked him about what kind of algorithmic questions do Microsoft ask, he told me "how would you sort a matrix to ensure that all elements are sorted by rows and by columns at the same time?" I didn't know he was kidding (he's speaking in Russian, I in Romanian, and sometimes I don't know Russian so well...), I actually thought this is Microsoft question so I starting to think (on paper of course):

Like in the old days at university I tried to look for a pattern, but I didn't found one, from the start I thought the problem is not solvable and tried to find a excuse not to solve it :) like "it's not practical etc.", on the next day, * tada *, the solution is fairly simple, it's like "treating all rows like one big array and just sort it":

So if you have a 3x3 matrix, you need to sort it by walking in this order: x00, x01, x02, x10, x11, x12, x20, x21, x22.
Of course you'll say: "big deal, what a stupid problem", yes it may be, it's a Bogosort after all, but it's fun to solve, or not...