Minimum local permutation data needed to globally merge locally sorted sequences?

Question

We have $k$ blocks of integer sequences $B_1,\dots,B_k$ where $B_i$ is a sequence $$a_{i,1},\dots,a_{i,n_i}$$ with $a_{i,j}\leq a_{i,j+1}$.

Denote the permutation matrix $M_{\ell,\ell'}$ that merges $B_\ell$ and $B_{\ell'}$ (there are more than one sometimes).

Assume for every pair $\ell,\ell'$ in $\{1,\dots,k\}$ we know at least one permutation matrix $M_{\ell,\ell'}$ that merges $B_\ell$ and $B_{\ell'}$.

From the $k(k-1)/2$ matrices it is possible to find the global permutation matrix $M$ that merges all the sequences. However it seems not all $k(k-1)/2$ matrices are needed.

$M$ is $n\times n$ permutation matrix where $n=n_1+\dots+n_k$. $M$ sorts every integer in all sequences. It is technically not full sorting here as all blocks are partially sorted. So we are doing merge like in mergesort. Thus I call this matrix $M$ merges all the blocks just as $M_{\ell,\ell'}$ merges blocks $B_\ell$ and $B_{\ell'}$ in sorted order. $M_{\ell,\ell'}$ is permutation matrix of size $n_{\ell,\ell'}\times n_{\ell,\ell'}$ where $n_{\ell,\ell'}=n_\ell+n_{\ell'}$.

1. Is it possible that only $O(k\log k)$ or may be just $o(k\log k)$ many $M_{\ell,\ell'}$ matrices suffice and is there a canonical construction of global $M$ from such minimal information? Or do we need $\Omega(k\log k)$ many $M_{ij}$?

2. Is the central case of $n_1=\dots=n_k=\frac{n_1+\dots+n_k}k$ any different?

Answer 1

1) Is it possible to choose $O(k\log k)$ matrices beforehand that will allow you to construct the global matrix M (sort all the elements of the $a_{i, j}$) regardless of the values of $a_{i, j}$?

No.

Even in the case $n_1 = n_2 = \ldots = n_k = 1$ (so in the setting of the usual sorting problem) if we don't know the order between two elements chosen beforehand we might not be able to sort all the numbers (for instance, those two elements may be the two least numbers in the set).

2)Is it possible to make an algorithm which sorts the numbers by using only $O(k\log k)$ matrices (but we don't know which ones)? Such an algorithm would be a generalization of the usual quick sorting algorithms.

In general, also no.

To see that, fix $k$, let $m = n_1 = n_2 = \ldots = n_k$ and suppose that each $B_i$ consists of $m$ numbers chosen (uniformly) randomly from $[0, 1].$ Assume that you've already sorted $A = B_3 \cup B_4 \cup \ldots \cup B_k$ and you also know how to merge $A$ with both $B_1$ and $B_2$ separately (in other words you know the odrer in $A \cup B_1$ and $A \cup B_2$). I claim that for $m >> k$ that doesn't determine the order on $A \cup B_1 \cup B_2$ which would imply that you need matrix $M_{1,2}$. Indeed, the order is determined if and only if for every pair of elements $b_1 \in B_1, b_2 \in B_2$ there is $a \in A$ such that either $$b_1 \le a \le b_2$$ or $$b_1 \ge a \ge b_2.$$ Now, as $m$ tends to infinity, the probability of this event is easily seen to be going to $0$ (since $\frac{|A|}{|B_1|} = \frac{|A|}{|B_2|} = k-2$). Therefore, there are some configurations where you need matrix $M_{1, 2}$ to sort all the elements. Moreover, if the probability of needing each specific matrix $M_{i, j}$ is at least $1-\epsilon$, then the probability of needing all the matrices is at least $1 - k(k-1)\epsilon$. That implies that for large $m$ you actually need all the matrices $M_{i, j}$ with high probability.

3)What would be the best way to sort a set of elements $B_1 \cup \ldots \cup B_k$ given that each $B_i$ is already sorted?

Probably by applying the regular MergeSort algorithm to this array. It works by sorting parts of the array and then merging them together which plays nicely with the fact that you already have $B_i$'s sorted.