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?