Is my algorithm a $O(nm \lg m)$ solution for sorting a row and columnwise sorted $2D$ array?
You should be careful using standard big-O analysis with more than one variable, I read a paper recently pointing out that this analysis can fail if certain assumptions are not met. In any case, let's assume for simplicity that $m$ is a power of 2. If it is not, the analysis will be very similar, just with some extra floors and other ugly stuff. In this case, we merge last two $n\times m/2$ arrays in time $2\cdot c\cdot (m/2)\cdot n$. Before that, we merged four (2x2) $n\times m/4$ arrays in time $4\cdot c\cdot (m/4)\cdot n$. Seeing the pattern, we add all of these times to get
$$\sum_{k=1}^{\log_2m}2^k\cdot c\cdot (m/2^k)\cdot n=\sum_{k=1}^{\log_2m}c\,m\,n=c\,m\,n\log_2m=O(n\,m\log m)$$
As a formality for the curious, I now cover the case where $m$ is not a power of 2. Then instead of two $n\times m/2$ arrays, we will have an array of size $n\times\lfloor m/2\rfloor$ and an array of size $n\times\lceil m/2\rceil$. Similarly, in the next step we get four arrays of sizes $n\times\left\lfloor\frac{\lfloor m/2\rfloor}{2}\right\rfloor$, $n\times\left\lceil\frac{\lfloor m/2\rfloor}{2}\right\rceil$, $n\times\left\lfloor\frac{\lceil m/2\rceil}{2}\right\rfloor$, and $n\times\left\lceil\frac{\lceil m/2\rceil}{2}\right\rceil$. Recursively, we have a runtime of
$$T(n,\,m)=T(n,\,\lfloor m/2\rfloor)+T(n,\,\lceil m/2\rceil)+c\,m\,n$$
Nobody wants to solve that, so I simply show that the complexity is still $O(n\,m\,\log m)$ if we take $m$ to be the next largest power of 2, call it $m'$. So I want to show that
$$\frac{n\,m'\,\log m'}{n\,m\,\log m}=O(1)$$
Say $m'=2^k$ and $m=f\cdot2^k$ for some $0.5\leq f&lt;1$ ($f$ as in fractional coefficient). We can write $m$ this way, since it is between $2^{k-1}$ and $2^k$ by construction of $m'$. This means that $m'=f^{-1}m$. Then we have
$$\frac{n\,m'\,\log m'}{n\,m\,\log m}=\frac{n\,f^{-1}m\,\log(f^{-1}m)}{n\,m\,\log m}=\frac{n\,f^{-1}m(\log m+\log f^{-1})}{n\,m\,\log m}=f^{-1}+\frac{f^{-1}\log f^{-1}}{\log m}=O(f^{-1}+f^{-1}\log f^{-1})=O(1)$$
Then the case when $m$ is a power of 2 can be applied in general.