Is my algorithm a $O(nm \lg m)$ solution for sorting a row and columnwise sorted $2D$ array?

Question

The problem (from MIT 6.006 course) is the following:

In this problem, you are given a $2D$ array of integers $A$ that has $n$ rows and $m$ columns. (Assume $m$ is much (e.g., exponentially) smaller than $n$.) Array $A$ has one special property: the integers in every row of $A$ and every column of $A$ are non-decreasing. More formally, $A[i, j] ≤ A[i, j + 1]$ for every $i = 1, 2, \ldots , n$ and $j = 1, 2, \ldots , m−1$, and $A[i, j] \leq A[i+1, j]$ for every $i = 1, 2, \ldots , n−1$ and $j = 1,2, \ldots ,m$.

Describe and analyze an algorithm with running time $O(nm \lg m)$ that produces a sorted $1$~$D$ array of length nm that has exactly the same elements as $A$. For example, for the $2D$ array given above, the algorithm should return $[1, 2, 3, 4, 4, 5, 5, 6, 8, 10, 19, 30]$.

The solution to this problem is to use the merge routine from merge-sort, along with a min-heap or an AVL tree.

This works by maintaining m pointers, one for each column of the $2D$ input array. The pointers start at the top of each column and we put each value of where the pointers point to into a min-heap (thus, the min-heap will at any given time contain at most m elements). We then use the merge routine from merge-sort to combine all the columns into a $1D$ array. The min-heap tells the merge routine which item to put next into the resulting array. When extracting an element from the heap, the pointer of the column of that element is advanced one element "down" and the corresponding value is inserted into the min-heap. This process is being performed until all the elements are processed.

I came up with a slightly different solution and was wondering if the time complexity still turns out to be $O(nm \lg m)$.

My solution works as follows (essentially a modified version of merge-sort):

• Start with the entire array
• Split the array in $2$ halfes by performing a column split (each of size $n \times m/2$)
• Recursively split the subproblems into halfes until we reach the base case
• Base case: the problem has size $n \times 1$ (a single column of the input array) and we simply return it (a $1D$ array that is already sorted)
• For every other step than the base case, merge the two $1D$ arrays into a $1D$ array that contains all the elements of the two columns but now sorted

Concerning the time complexity, my thoughts are:

• We split each subproblem into half the number of columns, thus resulting into $O(\log n)$ splits.
• At each level of the recursion we perform $O(nm)$ work (for merging).

Combining the two parts, this gives: $O(nm \lg m)$. Is this correct or am I missing something here?

My attempt:

$T(m,n) = 2T(\frac{m}{2}, n) + O(nm)$.
If I guess $O(nm \lg m)$ as a solution to this recurrence $\forall k$, $k < m$, this is what I get by induction:

\begin{align} T(m, n) &= 2T(\frac{m}{2}, n) + O(nm) \\ &= 2T(\frac{m}{2}, n) + c \cdot nm \\ &= 2(c \cdot n\frac{m}{2} \lg\frac{m}{2}) + c \cdot nm \\ &= c \cdot nm (\lg m - \lg 2) + c \cdot nm \\ &= c \cdot nm \lg m - c \cdot nm + c \cdot nm \\ &= c \cdot nm \lg m \end{align}

As far as I can see, this is the desired complexity but I still feel like I am missing something here.

Answer 1

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<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.