Sorting an array with x sorted subarrays

Question

I have been given two True/False questions regarding sorting an array. The questions are as following -

Question A

Given an array A with 3n keys that contains three equal parts A[1,n], A[n+1,2n] and A[2n+1,3n], each with n keys. Each part is sorted. Is possible to sort the keys of A into a new array B in O(n) steps (worst case)?

Question B

Given an array A with 10n keys that are comparable using a binary function that returns which element is bigger or if the elements are equal. The array is split into n equal parts, each with 10 keys. Each part is sorted. Is it possible to sort the keys of A into a new array B in O(n) steps (worst case)?

The solution to question A is that we can use merge() fucntion from MergeSort to sort the array.

The solution to question B is that it is not possible, as it violates the Ω(nlog(n)) lower bound for comparison based sorting algorithms

And I fail to see the difference between the two questions.. Is it because in question B we first need to apply the function? Why does it prohibits us from using merge() aswell? I don't see the logic behind the assumption that the two scenarios are different and I feel that I'm missing something important.

Answer 1

In the first exercise you have to merge a constant number of subarrays, i.e., $3$.

In the second exercise you'd have to merge $\Theta(n)$ subarrays, each of constant size. If you were able to produce a sorted version of the union of these subarray in time $O(n)$ using a comparison-based algorithm then you'd also have a comparison-based algorithm for the general sorting problem: Given a sequence of elements simply create $10$ copies of each element and sort the resulting sequence. Then drop the copies from the returned output.

Nothing prohibits you from also using merge() in the second case. It's just that you'd need to perform $\Omega(n)$ merges and the overall times spent will be $\Omega(n \log n)$. Consider for simplicity $n = 10 \cdot 2^k$. Even if you do the merges in a clever order (i.e., in a binary-tree fashion) you'd still need:

$$ \Omega\left( \sum_{i=0}^{k-1} 2^{k-i} \cdot (2 \cdot 10 \cdot 2^i - 1)\right) = \Omega\left(\sum_{i=0}^{k-1} 2^k\right) = \Omega(k2^k) = \Omega(n \log n) $$ comparisons.

Answer 2

Question A

ِYes just merge them in $\mathcal{O}(n)$.

Question B

Your problem reduced to merge $k$ sorted lists with $n$ elements, that can be done that in your problem can be done in $\mathcal{O}(n\log n)$.

Note that we can't do better than $\Omega(n\log n)$ because according to decision tree, number of leaves: $$\frac{n!}{(10!)^n}$$ So the height of the decision tree is $$\log\left(\frac{n!}{(10!)^n}\right)=\Omega(n\log n).$$