Somewhat-hardware-conscious algorithm for top k-of-n with $k=\Omega(\sqrt{n})$ 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.
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)$.