Path: utzoo!utgpu!jarvis.csri.toronto.edu!mailrus!ncar!ames!haven!adm!smoke!gwyn
From: gwyn@smoke.BRL.MIL (Doug Gwyn )
Newsgroups: comp.unix.questions
Subject: Re: sorting and reversing lines of a file
Message-ID: <9538@smoke.BRL.MIL>
Date: 28 Jan 89 09:17:41 GMT
References: <9056@burdvax.PRC.Unisys.COM> <810031@hpsemc.HP.COM>
Reply-To: gwyn@brl.arpa (Doug Gwyn (VLD/VMB) <gwyn>)
Organization: Ballistic Research Lab (BRL), APG, MD.
Lines: 13

In article <810031@hpsemc.HP.COM> gph@hpsemc.HP.COM (Paul Houtz) writes:
>Umm, please explain why sorting isn't the most eficient way to do this.

Because the general sorting utility does more work than is
necessary to simply reverse the order of the records (lines).
It's of order N*logN whereas only 2*N is required for this task.

The best approach for a specialized implementation would be to
make a preliminary sequential scan to find the positions of the
start of each line (and probably the line length), then in the
second phase seek to the appropriate start places and copy out
the lines.  You should also implement a smart buffering scheme
to make this approach maximally efficient.