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 in 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(n) \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?