Funnelselect: Cache-oblivious multiple selection

Sep 2023 (Written: Apr 2023)

Gerth Stølting Brodal and Sebastian Wild:

European Symposium on Algorithms (ESA) 2023

The multiple-selection problem asks to find several elements of given ranks in a list of unordered numbers. We present the first I/O-optimal cache-oblivious algorithm for this problem.

Our solution is a randomized algorithm related to (multiple) quickselect, but using a funnel (from (lazy) funnelsort) in reverse for I/O-efficient multiway partitioning.

Update

We found a deterministic algorithm with the same running-time complexities in our SWAT 2024 paper.