# To find median of $k$ sorted arrays of $n$ elements each in less than $O(nk\log k)$

How do I efficiently find the median of $$k$$ sorted arrays each of length $$n$$? Note that the total number of elements will be $$nk$$. I know it can be done in $$O(nk \log k)$$ time using merge technique. Is there a more efficient algorithm?

For two arrays it can be done in $$O(\log n)$$ time, but I can't see how to apply that here.

• Try aiming at a complexity of $O(k\log n)$. Commented Feb 4, 2018 at 9:48
• Try a divide-and-conquer approach similar to the Select Algorithm in linear time (CLRS). This would give a $O(nk)$ time. Commented Feb 5, 2018 at 0:55
• Since $x/\log x$ is increasing (for $x >e$) and $k \leq n$, we have that $k/\log k \leq n/\log n$, and so $k\log n \leq n\log k$. Commented Nov 17, 2020 at 14:26
• Please check my answer here. Commented Jan 18, 2023 at 21:10

Let us denote the arrays by $$A_1,\ldots,A_k$$, their sizes by $$|A_1|,\ldots,|A_k|$$, their medians by $$m_1,\ldots,m_k$$, and their union by $$\mathbf{A}$$. We will try to solve the following more general problem: given $$t$$, determine the $$t$$'th smallest element in $$\mathbf{A}$$.

Let $$m_r = \min(m_1,\ldots,m_k)$$ and $$m_s = \max(m_1,\ldots,m_k)$$. Define $$N = \sum_{i=1}^k \lceil |A_i|/2 \rceil.$$ There are at least $$N$$ many elements in $$\mathbf{A}$$ whose value is at least $$m_r$$, and at least $$N$$ many elements in $$\mathbf{A}$$ whose value is at most $$m_s$$.

If $$N \geq t$$ then elements larger than $$m_s$$ cannot be the $$t$$'th smallest element. In particular, we can throw out the upper half of $$A_s$$. Similarly, if $$N \geq n+1-t$$ then elements smaller than $$m_r$$ cannot be the $$t$$'th smallest element, and so we can throw out the lower half of $$A_r$$ (and update $$t$$ accordingly, by subtracting $$\lfloor |A_r|/2 \rfloor$$). Note that $$\min(t,n+1-t) \leq \lceil n/2 \rceil \leq N$$, and so at least one of these cases must happen.

How many rounds does it take this algorithm to complete? Each round results in reducing the size of one of the $$k$$ arrays roughly by half (the reduction is $$\ell \mapsto \lceil \ell/2 \rceil$$). One can check that it takes $$\lceil \log \ell \rceil$$ steps to reduce each array to a singleton. Therefore the number of rounds it takes the algorithm to narrow down all arrays to a single element is $$\sum_{i=1}^k \lceil \log |A_i| \rceil \leq k + \sum_{i=1}^k \log |A_i| \leq k + k \log \sqrt[k]{|A_1| \cdots |A_k|} \leq k + k \log \frac{|\mathbf{A}|}{k}.$$ After an initial round which takes $$O(k\log k)$$ time, each subsequent round can be implemented in $$O(\log k)$$, if we store the medians in an appropriate data structure such as a heap. Following this phase, we are left with $$k$$ elements, and we can run a linear time selection algorithm to find the $$t$$'th smallest element in $$O(k)$$. In total, this algorithm runs in time $$O\bigl(k\log k + k \log \tfrac{|\mathbf{A}|}{k}\bigr) = O(k\log |\mathbf{A}|).$$ When $$|A_i|=n$$ for all $$i$$, this is $$O(k\log (kn))$$.

• The trivial lower bound is $\log(nk)$. Commented Nov 18, 2020 at 10:44
• The algorithm finds the $t$’th smallest element. The parameter $t$ is updated as we go. Commented Nov 23, 2020 at 6:03
• This answer works for arrays of any size. They need not have identical sizes. Commented Jan 18, 2021 at 7:35
• The notation $|A_i|$ stands for the length of the array $A_i$. Commented Jan 18, 2021 at 10:57
• thats super nice. Since the # of rounds is O(k log (|A|/k)) and each round needs a min-heap operation (in log k) time, shouldnt the final complexity be O(n log k) for initial round + (log k)*k log (|A|/k) = O(k log k * log (|A|/k))? Commented Jan 18, 2023 at 17:12