Memory-efficient utility to return N first sorted values

Question

I would like to implement a very popular MapReduce example using only existing programs operating in a UNIX way. The problem is to find N most frequent values in an enormous amount of data. The generic solution on any general-purpose programming language is:

1. Map each value from the list to a tuple (value, 1).
2. Group same values summing up their counts.
3. Sort values by counts keeping top N frequent items.

For efficiency each step should fit into memory and be parallelized if possible. Thus I can use split, paste, xargs and sort from "core utils" and parallel from "more utils" for the first two steps still satisfying problem constraints. But in order to implement the last step I need always keep not more than N values simultaneously or else I will quickly run out of memory, so obviously I cannot use sort piped to head. A common approach is to use "priority queue" data structure, but is there a program for that?

Answer 1

GNU sort would benefit from a --range function to support this common operation: http://lists.gnu.org/archive/html/bug-coreutils/2009-07/msg00019.html

So I'd suggest to implement that in a local version of sort(1), and we'll merge it upstream too to make it generally available