Somewhat-hardware-conscious algorithm for top k-of-n with $k=\Omega(\sqrt{n})$

Question

The "top k of n" problem: You have n (not necessarily distinct) elements in an array, and you need to return another array containing the k elements with the highest value.

So, I'm going to need a top-k-of-n implementation for something I'm working on. Never mind exactly which programming language and hardware I'm going to use - but do mind that it's going to actually run on actual hardware. Thus there is multi-level caching so dereferencing pointers to arbitrary places should be minimized; there's the balance between computation and memory bandwidth to consider; there's multithreads/SIMDizing/whatever so I would like something parallelizable without too much communication... that's what I meant by somewhat-hardware-conscious.

Anyway, for a really small k I would probably just use a priority queue which fits in cache (or even linear search through several registers). But - what if your k is large? Large that the top k elements won't just be hiding at the top end of an estimated distribution? In this case I was thinking of estimating k using sampling, then (sort of) partitioning on that guess k; seeing how badly I missed; and iterating that, either partitioning my more-than-k or my more-than-n-minus-k. On one hand the length decreases quickly, and on the other hand I get closer to the really-small-k case, until I can settle for a priority queue (say for each core even) for the last bit.

So, my questions are:

• Can someone describe known algorithms for this variant of the problem, meeting my "vague hardware consciousness" constraint?
• Does the algorithm sketch I described sound like something you know?
• If not, does it sound like a good idea or can you describe shortcomings of this kind of an approach?

Notes:

• You may assume the data are non-negative integers if it helps in any way (I don't think it should), or make any any other reasonable assumptions.
• This problem is different that the partial sorting problem in that the output does not need to be sorted. Of course, for small k = $o(\sqrt{n})$ there isn't that much of a difference.
• The data is in memory, i.e. this is not a streaming algorithm and you can read data multiple times. You can't alter the input; you can make a full copy but hopefully that should be overkill.

Answer 1

If you're allowed to make multiple passes through the data, one efficient approach is to use QuickSelect to find the value of the $k$-th largest element, then follow with a linear scan that outputs all elements that are larger than it.

This is more or less a more carefully-worked out version of the kind of approach you seemed to be considering.

See also https://en.wikipedia.org/wiki/Selection_algorithm.

---

The following approach was written for an earlier version of the question, which specified $k = O(\sqrt{n})$, but might not be useful for large $k$:

Another possible approach would be to take a sorting network, which is a hardware circuit that sorts all of the values. Then, throw away all but the last $k$ outputs, and keep only the gates they depend on. You might be able to throw away a non-trivial fraction of the sorting network -- I haven't tried to work out how much. This would solve the partial sorting network, and could potentially be hardware-friendly.

---

The following approach was written for an earlier version of the question, which specified $k = O(\sqrt{n})$, but might not be useful for large $k$:

Another approach is to do something like merge sort, but where you only keep the top $k$ elements in each list at each stage. In other words, split your data so that each processor receives an equal number of items. Have each processor find the top $k$ of its elements (say, using a priority queue or any other method). Then merge lists recursively, where each merge operation merges two or more lists of size $k$ and outputs only the first (largest) $k$ elements of the result. This might work very well for out-of-cache (too-large-to-fit-in-main-memory) situations, or for parallel computing. If you can fit $B$ items in cache/memory, then each merge step merges $B/k$ lists, so the number of rounds is $\lg_{B/k} (n/B)$.