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

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?

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