Instant Sorting

In the May-June ’86 Issue of SyncWare News, I went through several sort routines for the 2068 and 1000 computers. For general use, I decided that the Shell-Faulk was the best all-round choice, but I also asked readers to send in any better ideas. One reader did, Larry Crawford of London, Ontarlo, Canada. He took the Shell-Faulk and converted it to machine code. Between the two of us, we have worked out bugs, shortened it, and made it more flexible. This routine will work on either the 2068 or Spectrum, but it should only take a little hacking to convert to a 1000.

Consorting with Speed

Let’s get right to the issue of speed. Below is a comparison of the Shell-Faulk in BASIC and machine code at sorting files which are each 10 characters long.

Files	BASIC	Machine Code
50	11.8 sec	.2 sec
100	29.9 sec	.3 sec
200	74.8 sec	.7 sec
400	184 sec	1.8 sec
800	430 sec	4.9 sec
1600	1049 sec	15 sec
3200	2402 sec	47 sec

Maybe instant isn’t the best word for it, but I think most people would be happy with this much speed. It works with any two dimensional string array (this is not for numbers – sorry) with any name and you can change the dimensions at will. A few BASIC statements relay certain key bits of Information to the machine code before it is called.

Sorting out the Code

First type in the following lines of BASIC:

   10 LET X=100: LET L=10: DIM N$ (X+1,L): FOR Z=1 TO X: FOR N=1 TO L: LET N$(Z,N)=CHR$ INT (65+RND*26): NEXT N: NEXT Z: PRINT "READY"; BEEP .5,40: PAUSE 0
   20 POKE 23296,X-256*INT (X/256): POKE 23297,INT (X/256): POKE 23298,L-256*INT (L/256): POKE 23299,INT (L/256): LET N$(X+1)=N$(X+1): POKE 23300,PEEK 23629: POKE 23301,PEEK 23630
   30 LET N$(1)=N$(1): RANDOMIZE USR 61402
  100 BEEP .5,30: FOR Z=1 TO X: PRINT N$(Z): NEXT Z: STOP
 9990 CLEAR 61389: LOAD "sort"CODE 61390: GO TO 1
 9999 SAVE "SORT" LINE 9990: BEEP .5,40: SAVE "sort"CODE 61390,249: BEEP .5,40: CLS: PRINT "REWIND TO VERIFY": VERIFY "SORT": VERIFY "sort"CODE 61390,249

Line 10 just sets up some random files for testing purposes as was done in the BASIC version of the sort. One change is that we dimension N$ for one extra file space. Thus, if X=100 we actually dimension N$(101,L). This extra space is only used as a temporary storage area as files are moved. Never use it to store data. Be sure to set up this extra file space in your own programs too. As you test this program, feel free to set X (the number of files) and L (the length of files) to any values the computer has room for. If your own programs do not use N$ for storage, just change all references to N$ to be the name you want. The same applies to the use of X and L.

Line 20 begins the part of the routine you use in your own programs. It sets up the machine code pointers beginning with POKE 23296 and 23297 with the number of files to sort (X) not including the extra file. You could POKE a lower value than X if you only wanted to sort some of the files such as the first 50. Next we POKE the length of each file into 23298 and 23299. The two storage areas for size and length are to allow values larger than 255. This way you can have thousands of values of considerable length.

The statement LET N$(X+1)=N$(X+1) is used to make the computer store the address of the extra file in a special place called “dest”. This is found at 23629 and 23630. Therefore we take the contents of those addresses and put them in 23300 and 23301 so the machine code can access it later.

All these POKES are made into the printer buffer as are all varlables created by the machine code itself. This is one reason the program is completely relocatable. If you do relocate the machine code, do not change the location of any POKEs!

… file to sort, but instead of poking the location as before, we let the machine code access “dest” directly. You can make the routine start sorting after the first file If you wish. To start with the 11th file, just make the statement read: LET N$(11)=N$(11). Also be sure you have adjusted the total number of files to sort as well. If X=100, then by starting at file number 11, we would only sort 90 files. Without this correction, the routine would overwrite other variables. The machine code is then called and the sorting is done.

Lines 20 and 30 are the only BASIC lines you need to use this in your own programs. The actual line numbers are not important and the two lines can be combined if you wish. The remaining lines are only used to allow you to practice on this example, but are not needed in your programs. Line 100 prints out the sorted files. Line 9999 is for making a copy of the program (enter RUN 9999) and verifying it after the machine code is in place. When reloaded, line 9990 sets RAMTOP and loads the machine code. The test procedure then begins. Depending on the values you set for X and L, the setup can take quite some time – certainly longer than the sorting process. After you have saved a copy, you can test without reloading by entering RUN.

The machine code can be moved to any position you prefer as long as you have room for 249 bytes. Remember that the RANDOMIZE USR address must be 12 bytes past the start of the machine code. If you load it in at 65000, then RANDOMIZE USR 65012. Also adjust the save and load commands to reflect the change.

To enter the machine code, first enter CLEAR 61389. Now enter the following lines which will load the machine code beginning at 61390:

 1000 FOR N-61390 TO 61638
 1010 INPUT "ENTER NUMBER ";P
 1015 POKE N,P
 1020 PRINT N;" ";P
 1030 NEXT N
 1040 STOP

Now enter RUN 1000 and then enter one number at a time as listed below. The numbers are listed in order horizontally so finish the first row ACROSS before going to the second line.

[See original article for list of codes]

When all the numbers have been entered, delete all lines from 1000 to 1040 and make your backup copy before testing the program.

MC Explained

The logic of the machine code closely follows that of the BASIC version. As I explain the machine code, I will refer to the original BASIC version often so here is a listing of the sort portion of that routine so you can better follow along:

 1050 LET M-X: LET S-M
 1100 LET S-INT (S/2): IF S<1 THEN GO TO 9900
 1115 IF S/2=INT (S/2) THEN LET S=S+1
 1120 FOR N=1 TO M-S: LET J=N
 1150 IF N$(J)>N$(J+S) THEN LET D$=N$(J): LET N$(J)-N$(J+S): LET N$(J+S)=D$: LET J-J-S: IF J>0 THEN GO TO 1150
 1160 NEXT N: GO TO 1100

Here is a description of the machine code:

EFCE LD DE,5B00     ; The start of the machine code is at 61390. 
                    ; This is actually the end of the sort where 
                    ; the printer buffer is cleared of data. DE 
                    ; is set to the start of the buffer which is 
                    ; also the start of the machine code variables.
EFD1 LD HL,5B16     ; HL is set to a point in the buffer that is 
                    ; not affected by the me and still contains zeros.
EFD4 LD BC,0015     ; BC holds the number of bytes affected by the 
                    ; machine code routine.
EFD7 LDIR           ; This command moves whatever is in the address 
                    ; represented by HL into the DE address. HL and 
                    ; DE are each incremented to the next address 
                    ; while BC is reduced by 1. This repeats until 
                    ; BC=0 which also means the buffer is clear so 
                    ; your next LPRINT won't print any garbage.
EFD9 RET            ; Return to BASIC (sort done)
EFDA LD HL, (5B00)  ; The actual sort starts here from BASIC (address 
                    ; 61402). HL is loaded with the value of X which 
                    ; was poked into 5B00 from BASIC.
EFDD LD,(5B0A),HL   ; Put X in storage for M. Same as M=X in line 1050.
EFE0 LD (5B0C),HL   ; Also put in storage for S. Same as S=M in line 1050.
EFE3 LD HL,(5B0C)   ; This starts line 1100. Get value of S.
EFE6 XOR A          ; Clears carry flag before RR instruction and zero 
                    ; the A register.
EFE7 RR H
EFE9 RR L           ; These 2 instructions get the integer value of 
                    ; HL/2. Thus it is the same as INT (S/2) in 1100.
EFEB LD A,H
EFEC OR L 
EFED JR Z,EFCE      ; If HL=0 (S=0) then sort is done so jump to clear 
                    ; printer buffer before returning to BASIC.
EFEF SET 0,L        ; Set bit 0 of L to make sure it is an odd value (line 1115).
EFF1 LD (5B0C),HL   ; Store new value of S.
EFF4 PUSH HL        ; Put S on stack.
EFF5 EX DE,HL       ; Put S value in DE
LD HL,(5B0A)        ; Get M value
EFF9 XOR A          ; Clear carry flag before subtraction.
EFFA SBC HL,DE      ; Calculate M-S
EFFC LD (5B0E),HL   ; Store M-S
EFFF LD HL,0001     ; Prepare for FOR-NEXT loop
F002 LD (5B10),HL   ; Store in N. The loop starts as N-1
F005 LD (5B12),HL   ; Put in J (J=N). See line 1120
F008 LD HL,(5C4D)   ; 5C4D is the address of "dest", so this shows were
                    ; the first file is.
F00B LD (5B06),HL   ; Store address of first file in N$(J)
FOOE LD DE,(5B02)   ; Get length of each file
F012 POP BC         ; Get S value
F013 ADD HL,DE
F014 DEC BC
F015 LD A,B
F016 OR C
F017 JR NZ,F013     ; These lines find the address of file N$(J+S)
F019 LD (5B08),HL   ; Store N$(J+S) address. See 1150
F01C LD DE,(5B06)   ; Get N$(J) address
F020 LD BC,(5B02)   ; Get file length
F024 LD A,(DE)      ; Get a character from N$(J) file
F025 CP (HL)        ; Compare to character in N$(J+S) file
F026 JR C,F033      ; Jump if the order is okay to preparation for NEXT N
F028 JR NZ,F068     ; Jump to swap routine if order is wrong
F02A DEC BC         ; If the characters are the same then we continue to 
                    ; compare the two files by first decrementing the number
                    ; of file characters to check.
F02B LD A,B
F02C OR C
F02D JR Z,F033      ; These lines check to see if BC=0, thus all characters
                    ; are checked. If so then jump to NEXT N.
F02F INC DE
F030 INC HL
F031 JR F024        ; To continue comparing the two files, we move HL and
                    ; DE to the next characters and jump back to compare
                    ; again.
F033 LD A,(5B14)    ; This starts the preparation for NEXT N.
F036 DEC A          ; Since the FLAG was either zero or one,
                    ; this will make it zero or 255.
F037 JR NZ,F044     ; If it is 255, the flag was not set so jump to NEXT N.
F039 POP HL         ; If the flag was set, get old N$(J+S) address.
                    ; This is the address before we did LET J=J+S
                    ; in line 1150.
F03A LD (5B08),HL   ; Store LET J=J+S in line 1150.
F03D POP HL         ; Get old N$(J) -  what it was before LET J=J-S.
F03E LD (5B06),HL   ; Store in N$(J)
F041 LD (5B14),A    ; The A register is zero so this clears the FLAG.
F044 LD HL,(5B10)   ; NEXT N begins here. First get old N value.
F047 INC HL         ; To next value of FOR-NEXT loop
F048 LD (5B10),HL   ; Store new N value
F04E EX DE,HL       ; Put J value in DE
F04F LD HL,(5B0E)   ; Get M-S value
F052 XOR A          ; Clear carry flag
F053 SBC HL,DE      ; Subtract (M-S)-J to see if FOR-NEXT is done.
F055 JR C,EFE3      ; If J is more than M-S, then the loop is done,
                    ; so jump back to mc version of line 1100.
F057 LD HL,(5B06)   ; If loop is not done, get N$(J) address.
F05A LD DE,(5B02)   ; Get length of file
F05E ADD HL,DE      ; Puts HL at next file
F05F LD (5B06),HL   ; Store new N$(J) address
F062 LD HL,(5B08)   ; Get N$(J+S) address
F065 ADD HL,DE      ; HL at next file (new N$(J+S) address)
F066 JR F019        ; Go back and sort again
F068 LD HL,(5B06)   ; Start the file swap here. Get N$(J) address.
F06B LD DE,(5B04)   ; Load DE with the extra N$ file address, which
                    ; is used as D$ in the BASIC version.
F06F LD BC,(5B02)   ; Get file length so we know how many bytes to move.
F073 PUSH DE        ; Save D$ address
F074 PUSH BC        ; Save file length
F075 PUSH HL        ; Save N$(J) address
F076 LDIR           ; Put file N$(J) in D$
F078 LD HL,(5B08)   ; Get N$(J+S) address
F07B POP DE         ; Get N$(J) address
F07C POP BC         ; Get length of file
F07D PUSH HL        ; Save N$(J+S)
F07E PUSH BC        ; Save length
F07F LDIR           ; Put N$(J+S) in N$(J)
F081 POP BC         ; Get length
F082 POP DE         ; Get N$(J+S) address
F083 POP HL         ; Get D$ address
F084 LDIR           ; Put D$ in N$(J+S)
F086 LD HL,(5B12)   ; Get J value
F089 LD DE,(5B0C)   ; Get S value
F08D XOR A          ; Clear carry flag
F08E SBC HL,DE      ; Calculate J-S
F090 LD (5B12),HL   ; Store new J value
F093 JR C,F033
F095 JR Z,F033      ; If J is less or equal to zero, the to prep fN.
F097 LD A,(5B14)    ; This starts our preparation to go to line 1150.
                    ; First get FLAG
F09A CP 0           ; Compare FLAG to zero
F09C JR NZ,F0AA     ; Jump if FLAG already set
F09E LD HL,(5B06)   ; If FLAG is not set, we must save the present
                    ; address of N$(J), so first get N$(J) address.
F0A1 PUSH HL        ; Save N$(J) address
F0A2 LD HL,(5B08)   ; Get N$(J+S) address to save too
F0A5 PUSH HL        ; Save it
F0A6 INC A          ; Make A register hold 1
F0A7 LD (5B14),A    ; Use it to set FLAG
F0AA LD HL,(5B06)   ; Get N$(J) address
F0AD LD (5B08),HL   ; Put it in N$(J+S). This allows for LET J=J-S.
F0B0 PUSH HL        ; Save address of N$(J+S)
F0B1 LD BC,(5B02)   ; Get file length
F0B5 LD DE,(5B0C)   ; Get S value
F0B9 XOR A          ; Clear carry flag
F0BA SBC HL,BC
F0BC DEC DE
F0BD LD A,D
F0BE OR E
F0BF JR NZ,F0B9     ; These adjust the address of N$(J) because of 
                    ; the LET J=J-S command
F0C1 LD (5B06),HL   ; Store new N$(J) address
F0C4 POP HL         ; Get N$(J+S) address
F0C5 JR F066        ; Now go back to sort again. The jump is too far for
                    ; a relative jump so it is done in two steps. First 
                    ; to F066 which then goes to F019.

The variables are all found in the printer buffer as follows:

5B00-5B01	23296-7	X value from BASIC
5B02-5B03	23298-9	Length of file from BASIC
5B04-5B05	23300-1	Extra file address from BASIC
5B06-5B07	23302-3	N$(J) address
5B08-5B09	23304-5	N$(J+S) address
5B0A-5B0B	23306-7	M value
5B0C-5B0D	23308-9	S value
5B0E-5B0F	23310-11	M-S value
5B10-5B11	23312-13	N value
5B12-5B13	23314-5	J value
5B14	23316	FLAG

As always, let me know if you have any better ideas (BASIC or machine code).