Finding the k-th smallest ternary sum of elements from three different arrays The problem goes like this:

Given arrays $\{ a_i: 0\leq i \leq n-1 \},\{ b_i: 0\leq i \leq n-1 \} $ and  $\{ c_i: 0\leq i \leq n-1 \}$, we want to know what is the $k$-th smallest combination $a_r+b_s+c_t$ where $r, s, t$ are arbitrary indices.

Since $k$ is relatively much smaller than $n^3$ (we may suppose $k \approx n $ for simplicity), it would be wasteful to: naively enumerate all $n^3$ possibilities and find the $k-$th smallest using a binary heap.

What is a more efficient way (in terms of time complexity) to solve this problem? I try to optimize the naive algorithm described above by first sorting three arrays then do the heaping for $\{ a_r + b_s + c_t: r+s+t &lt; k \}$, but I believe this is far from a most efficient algorithm. Thanks.

(Rmk: the algorithm is intended to be comparison-based, since elements might be non-integers.)
You can first sort the three arrays. In the following answer we assume these arrays are already sorted.

You can maintain a priority queue $Q$. Initially it contains only $a_0+b_0+c_0$. Then in each iteration, you pop the smallest element (say $a_r+b_s+c_t$), and add $a_{r+1}+b_s+c_t$, $a_r+b_{s+1}+c_t$ and $a_r+b_s+c_{t+1}$ (duplicates are not allowed, while it is easy to check whether a combination already exists in $Q$). Now we can claim the popped sum in the $i$-th iteration is the $i$-th smallest sum. 

This algorithm takes $O(n\log n)$ time. If the given three arrays are already sorted, the time is reduced to $O(k\log k)$.

We can use mathematical induction on $i$ to prove the correctness. Suppose the $i$-th smallest sum is $a_r+b_s+c_t$, then we have the following chain:

\begin{align}
&amp;a_0+b_0+c_0\\
\le\ &amp;a_1+b_0+c_0 \\
\le\ &amp;\cdots \\
\le\ &amp;a_r+b_0+c_0 \\
\le\ &amp;a_r +b_1+c_0 \\
\le\ &amp;\cdots \\
\le\ &amp;a_r +b_s+c_0 \\
\le\ &amp;\cdots \\
\le\ &amp;a_r+b_s+c_t.
\end{align}

For convenience, we denote by $S_0,\ldots,S_{\ell}$ these sums in the chain. Let $S_j$ be the first sum in the chain that is not popped before the $i$-th iteration. Then in the iteration that $S_{j-1}$ is popped, $S_j$ is added to $Q$ according to our algorithm. This means the sum popped in the $i$-th iteration must be no more than $S_j$, thus no more than $S_{\ell}=a_r+b_s+c_t$. By inductive assumption, the first $i-1$ smallest sums are popped before the $i$-th iteration, so the sum popped in the $i$-th iteration is exactly the $i$-th smallest sum.