<p>The algorithm described by Frederickson and Johnson in 1982 considers that all sets have the same size. They also described in 1980 an optimal solution that takes advantage of the different sizes of the sorted sets. The complexity of this algorithm is within $O(k + \sum^k_{i=1}\log{n_i})$.</p>

<p><strong>Reference</strong></p>

<p>Greg N. Frederickson and Donald B. Johnson. 1980. Generalized selection and ranking (Preliminary Version). In Proceedings of the twelfth annual ACM symposium on Theory of computing (STOC '80). ACM, New York, NY, USA, 420-428. DOI=10.1145/800141.804690 <a href="http://doi.acm.org/10.1145/800141.804690" rel="nofollow">http://doi.acm.org/10.1145/800141.804690</a></p>

CC BY-SA 3.0
2015-07-29T01:54:28.560Z
2015-07-29T01:54:28.560Z
Carlos Ochoa
<p>Frederickson and Johnson obtained an optimal result in the 80s. Let $p=\min(k,t)$, then there exist an algorithm solves your problem in $O(k+p \log \frac{t}{p})$. </p>

<p><strong>Reference</strong></p>

<p>G.N. Frederickson, D.B. Johnson "<a href="http://www.sciencedirect.com/science/article/pii/0022000082900484">The complexity of selection and ranking in x+y and matrices with sorted columns</a>" 
J. Comput. System Sci., 24 (2) (1982), pp. 197–208</p>

CC BY-SA 3.0
2014-02-09T02:58:32.423Z
2014-02-09T02:58:32.423Z
Chao Xu
<p>The k=2 case comes up in parallel merge sort since the merging of two sorted arrays from different threads needs to be split up among two threads to maintain the same amount of parallelism. <a href="http://www2.myoops.org/twocw/mit/NR/rdonlyres/Electrical-Engineering-and-Computer-Science/6-046JFall-2005/30C68118-E436-4FE3-8C79-6BAFBB07D935/0/ps9sol.pdf" rel="nofollow">This homework solution</a> is one reference.</p>

CC BY-SA 3.0
2015-07-11T19:17:45.560Z
2015-07-11T19:17:45.560Z
KWillets
<p>I am looking for bibliographic references for the following algorithm/problem: I named it "BiSelect" or "t-ary Select" or "Select in Union of Sorted Arrays", but I guess it was introduced before under another name?</p>

<h2>Problem</h2>

<p>Consider the following problem:</p>

<blockquote>
  <p>Given $k$ disjoint sorted arrays $A_1,\ldots, A_k$, of respective sizes $n_1,\ldots,n_k$, and an integer $t\in[1..\sum n_i]$, what is
  the <strong>$t$-th value of their sorted union</strong> $\cup_i A_i$?</p>
</blockquote>

<h2>Solutions</h2>

<p>There is a very simple and elegant algorithm running in time $O(\lg\min\{n_1,n_2,t\})$ if $k=2$: if $k=2$, just compare $A_1[t/2]$ with $A_2[t/2]$ and recurse on $A_1[t/2..t]$ and $A_2[1..t/2]$ or $A_1[1..t/2]$ and $A_2[t/2..t]$ accordingly, in both cases with parameter $t/2$ (and some minor optimizations when $n_1$ or $n_2$ are smaller than $t$).</p>

<p>This generalizes to a slightly more sophisticated algorithm running in time $O(k\lg t)$ for larger values of $k$, based on computing the median of the values $A_i[t/k]$ for $i\in[1..k]$: the $t/k$  smallest elements can be further ignored in the $k/2$ arrays where $A_i[t/k]$ is smaller than the median, and the elements of ranks in $[t-t/k..]$ can be further ignored in the $k/2$ other arrays, resulting in a halving of $t$ in each recurrence (and a cost of $O(k)$ for the median).</p>

<h2>References?</h2>

<p>I am happy with my solution(s), but I suppose that the problem (and its solution) was already known. It is related to the linear time algorithm for computing the median (by sorting groups of size $5$, and recurse on the median of their middles), but is slightly more general. I asked several colleges at Madalgo in Aarhus (Denmark), and then some others at the workshop Stringology (Rouen), without success:  I am hoping that someone more knowledgeable might help on Stack Exchange... </p>

<h2>Motivations</h2>

<p>Solutions to this problem have applications to Deferred Data Structure on arrays (indeed, it can be seen as an operator in a deferred data structure for the union of sorted arrays); and in a more convoluted way, to the adaptive computation of optimal prefix free codes.</p>

<reference-request>
Select in union of sorted arrays: Already known?
J.y B.y
# Select in union of sorted arrays: Already known?

(Asked by: username_0 on 2014-02-08)

I am looking for bibliographic references for the following algorithm/problem: I named it "BiSelect" or "t-ary Select" or "Select in Union of Sorted Arrays", but I guess it was introduced before under another name?

## Problem

Consider the following problem:

> Given $k$ disjoint sorted arrays $A\_1,\ldots, A\_k$, of respective sizes $n\_1,\ldots,n\_k$, and an integer $t\in[1..\sum n\_i]$, what is
> the **$t$-th value of their sorted union** $\cup\_i A\_i$?

## Solutions

There is a very simple and elegant algorithm running in time $O(\lg\min\{n\_1,n\_2,t\})$ if $k=2$: if $k=2$, just compare $A\_1[t/2]$ with $A\_2[t/2]$ and recurse on $A\_1[t/2..t]$ and $A\_2[1..t/2]$ or $A\_1[1..t/2]$ and $A\_2[t/2..t]$ accordingly, in both cases with parameter $t/2$ (and some minor optimizations when $n\_1$ or $n\_2$ are smaller than $t$).

This generalizes to a slightly more sophisticated algorithm running in time $O(k\lg t)$ for larger values of $k$, based on computing the median of the values $A\_i[t/k]$ for $i\in[1..k]$: the $t/k$ smallest elements can be further ignored in the $k/2$ arrays where $A\_i[t/k]$ is smaller than the median, and the elements of ranks in $[t-t/k..]$ can be further ignored in the $k/2$ other arrays, resulting in a halving of $t$ in each recurrence (and a cost of $O(k)$ for the median).

## References?

I am happy with my solution(s), but I suppose that the problem (and its solution) was already known. It is related to the linear time algorithm for computing the median (by sorting groups of size $5$, and recurse on the median of their middles), but is slightly more general. I asked several colleges at Madalgo in Aarhus (Denmark), and then some others at the workshop Stringology (Rouen), without success: I am hoping that someone more knowledgeable might help on Stack Exchange...

## Motivations

Solutions to this problem have applications to Deferred Data Structure on arrays (indeed, it can be seen as an operator in a deferred data structure for the union of sorted arrays); and in a more convoluted way, to the adaptive computation of optimal prefix free codes.

**Tags:** reference-request


---

## 3 answers

### Answer by username_1 on 2015-07-29. Score: 2 | Accepted answer

The algorithm described by Frederickson and Johnson in 1982 considers that all sets have the same size. They also described in 1980 an optimal solution that takes advantage of the different sizes of the sorted sets. The complexity of this algorithm is within $O(k + \sum^k\_{i=1}\log{n\_i})$.

**Reference**

Greg N. Frederickson and Donald B. Johnson. 1980. Generalized selection and ranking (Preliminary Version). In Proceedings of the twelfth annual ACM symposium on Theory of computing (STOC '80). ACM, New York, NY, USA, 420-428. DOI=10.1145/800141.804690 <http://doi.acm.org/10.1145/800141.804690>


---

### Answer by username_2 on 2014-02-09. Score: 21

Frederickson and Johnson obtained an optimal result in the 80s. Let $p=\min(k,t)$, then there exist an algorithm solves your problem in $O(k+p \log \frac{t}{p})$.

**Reference**

G.N. Frederickson, D.B. Johnson "[The complexity of selection and ranking in x+y and matrices with sorted columns](http://www.sciencedirect.com/science/article/pii/0022000082900484)"
J. Comput. System Sci., 24 (2) (1982), pp. 197–208


---

### Answer by username_3 on 2015-07-11. Score: 0

The k=2 case comes up in parallel merge sort since the merging of two sorted arrays from different threads needs to be split up among two threads to maintain the same amount of parallelism. [This homework solution](http://www2.myoops.org/twocw/mit/NR/rdonlyres/Electrical-Engineering-and-Computer-Science/6-046JFall-2005/30C68118-E436-4FE3-8C79-6BAFBB07D935/0/ps9sol.pdf) is one reference.


---

