Abstract
Selection and sorting the Cartesian sum, $X+Y$, are classic and important
problems. Here, a new algorithm is presented, which generates the top $k$
values of the form $X_i+Y_j$. The algorithm relies only on median-of-medians
and is simple to implement. Furthermore, it uses data structures contiguous in
memory, and is fast in practice. The presented algorithm is demonstrated to be
theoretically optimal.