2
$\begingroup$

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?

$\endgroup$
2
$\begingroup$

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

| cite | improve this answer | |
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.