[thaumasiotes]

> Something as basic as finding the largest N elements in a array isn't a trick, it's something that should be painfully obvious to anyone who's coded for more than a month.

Not a trick? Of course it's a trick.

The efficient way to do it is to heapsort the array, but just stop after you've popped N elements from the heap.

You can do much worse and still stay in pure linear time (though as I noted in another response to you, the difference in polynomial order between O(n) and the O(n log n) that would be required to finish your heapsort is ε, where ε is larger than zero but smaller than any real number): just scan the array N times, looking for the largest element that's smaller than your shrinking upper bound. I'd rather see a solution that sorted than one that took N passes to pull N elements -- sorting will be faster -- but the N passes approach is pure linear time.

Then again, naive N passes will fail when the array contains duplicates. To avoid that, you'll need to allocate a data structure to hold your N answers, and implement a way of adding values in and having it appropriately discard the lowest value when you add to it while it's full. That's starting to look like a trick. It also cuts you down to one pass.

Is the "not a trick" answer you're looking for implementing an N-running-maxes data structure, or remembering how to heapsort? Do you really care about getting your results in slow linear time instead of fast "so close to linear you can't even tell the difference" time?