sort suggestion : --head/tail n option

[Philippe De Muyter]

Hello,

I am considering adding a new option to the GNU `sort' utility :

the goal is to produce only the first or the last n lines of the sorted
output.  Thus the result should be exactly equal to

        sort <sort-options> | tail -n
or
        sort <sort-options> | head -n

I am proposing to name this mutually exclusive options

        --head n        prints only the first n lines of the sorted output
        --tail n        prints only the last n lines of the sorted output

The goal is to avoid `sort' the cost of sorting the rest of the inputs.
It is indeed useless and costly to sort 100000 lines if one just needs the
10 first/last.

My implementation idea is to use a heap of n entries, filling it with the
first n inputs, sorted such that the top of the heap is the nth or the nth
to last in the current virtual output, and then comparing the following
inputs with the top of the heap, either discarding the new input,
or removing the top of the heap and inserting the new input in the heap.

At the end of all inputs we are left with exactly n inputs half-sorted in
a heap, that we must thus finish to sort.

I have done some speed tests with an adhoc strcmp-only sort program and
on a Pentium(R) 4 2.40GHz, I get e.g. :

        $ ls -U | wc -l
         109694
        $ time ls -U | /tmp/lastn -1000 > /dev/null
        real    0m0.437s
        user    0m0.136s
        sys     0m0.098s
        $ time ls -U | sort | tail -1000 > /dev/null
        real    0m5.252s
        user    0m1.759s
        sys     0m0.107s

Do you think that this new option would fit easily in the current `sort'
implementation, and how ?

Best Regards

Philippe

Philippe De Muyter  phdm at macqel dot be  Tel +32 27029044
Macq Electronique SA  rue de l'Aeronef 2  B-1140 Bruxelles  Fax +32 27029077