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