Array[3][3]

Sort a 2d array(m*n). Such that if we print the array in zigzag manner you get the sorted array(first row than second row and so on..). The array being such that each of its rows and its cols are in increasing order
e.g
I/P:
2 4 5
3 6 8
5 7 9

O/P:
2 3 4
5 5 6
7 8 9

Solution :
O(m*n*log(n))
Since the rows are sorted we can do this...
Take Row[0] and Row[1] merge them, Row [2] Row[3] merge them.....
so the tree looks like this.... Row[i,j] implies that Row[i] through Row[j] are sorted(i.e if we go from Row[i][0] till Row[j][n-1] it will be in sorted manner)...
___________________________Row[0,n-1]
___________________________/______.
.
.
___________/______________\___________
______Row[0,1]___________Row[2,3]_________________Row[n-2,n-1]
_____/________\________/_________\________________/__________Row[0]____Row[1]___Row[2]___Row[3]_____________Row[n-2]___Row[n-1]

This is similar to To merge sort of m*n elements only differernce is that we already have sorted arrays and thus we reduce the height of our merge tree....