External sorts

 BBS: Inland Empire Archive
Date: 04-01-92 (20:07)             Number: 140
From: CHARLES GRAHAM               Refer#: NONE
  To: ALL                           Recvd: NO  
Subj: External sorts                 Conf: (2) Quik_Bas

There are a number of reasonably efficient sorting
algorithms available for sorting data when all records are
contained inside an array, all at the same time. Such
internal sorts are fast and pretty straightforward.

But lately I've gotten interested in external sorts, i.e.,
sorting data that is never all in an array, all at the same
time. The following is such a sort, based on the standard
Shell Sort algorithm. It assumes there is a random-access
file of 1125 fixed-length, 60-byte records called
MERGADDR.FIL.

'XTERSORT.BAS Charles Graham, 1992
DEFINT A-Z
CONST True = -1
CONST False = NOT True
NumRecs = 1125
Gap = INT(NumRecs / 2)
RecLen = 60
File$ = "MERGADDR.FIL"
OPEN File$ FOR RANDOM AS 1 LEN = RecLen
FIELD #1, RecLen AS Rec$
DO
    DO
        MadeSwap = False
        FOR Count = 1 TO NumRecs - Gap
            GET #1, Count
            LowRec$ = Rec$
            GET #1, Count + Gap
            HighRec$ = Rec$
            IF LowRec$ > HighRec$ THEN
                LSET Rec$ = LowRec$
                PUT #1, Count + Gap
                LSET Rec$ = HighRec$
                PUT #1, Count
                MadeSwap = True
            END IF
        NEXT Count
    LOOP UNTIL NOT MadeSwap
    Gap = INT(Gap / 2)
LOOP WHILE Gap > 0
CLOSE
END

It works flawlessly. What's the problem? Since physical
read and write operations to disk are orders of magnitude
slower than logical operations inside main memory, the sort
is _real_ slow.

So I was wondering if any of you had already developed some
fine-tuned code for external sorting. I'd be interesting in
seeing whatever you had.


--- QM v1.30
 * Origin: QuikCom * St Charles MO * HST/V32 (1:100/602.0)