What is the difference in time-complexity for sorting these 2-d arrays?

Question

Let $A$ have $n/10$ rows, $10$ columns and $n$ overall elements

Let $B$ have 10 rows, $n/10$ columns and $n$ overall elements.

It is given that each row is sorted in ascending order, Can you sort each of these in $O(n\log(n))$ or better using comparison sort?

I'm leaning towards k-way merge implementing a min-heap following this implementation merging sorted arrays, but I can't seem to figure out what the difference between this cases is.

$B$ for example will have $10$ elements constantly in the min-heap, so the time complexity will be $10n \log(10) \in O(n)$? Is this even possible in comparison sorts?

While $A$ would have $n/10$ elements in the min-heap, but are the run times equivalent?

Answer 1

The algorithm you suggest for $B$ is a comparison-based algorithm with complexity $O(n \log h)$, where $h$ is the maximum number of elements in the heap. Since $h = \Theta(1)$, you have that $B$ can be sorted in time $O(n)$.

Regarding $A$, the lower bound of $\Omega(m \log m)$ on any comparison-based algorithm that sorts $m$ elements still applies. Indeed, the first elements on each row (i.e., those of the first column) can be in any order relation with one another.

Any algorithm that sorts $A$, is also an algorithm that sorts the $m = \frac{n}{10} = \Theta(n)$ elements in the first column, and therefore it must have time $\Omega(m \log m) = \Omega(n \log n)$.