--- title: "Instant Sorting" type: "article" slug: "instant-sorting" url: "http://localhost/article/instant-sorting/" markdown_url: "http://localhost/article/instant-sorting.md" published_at: "2021-08-28T14:07:38+00:00" modified_at: "2026-07-21T17:57:32+00:00" featured_image: url: "http://localhost/wp-content/uploads/2022/04/20230809-041332.jpg" excerpt: "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…" category: - name: "SyncWare News" slug: "syncware-news" taxonomy: "category" url: "http://localhost/category/periodicals/syncware-news/" post_tag: - name: "Best of Timex/Sinclair 2068 Articles and Documents" slug: "ts2068best" taxonomy: "post_tag" url: "http://localhost/tag/ts2068best/" - name: "Downloadable" slug: "downloadable" taxonomy: "post_tag" url: "http://localhost/tag/downloadable/" - name: "Machine language programming" slug: "machine-language" taxonomy: "post_tag" url: "http://localhost/tag/machine-language/" - name: "TS 2068" slug: "ts2068" taxonomy: "post_tag" url: "http://localhost/tag/ts2068/" - name: "Type-in program" slug: "type-in-program" taxonomy: "post_tag" url: "http://localhost/tag/type-in-program/" model: - name: "Timex/Sinclair 2068" slug: "ts-2068" taxonomy: "model" url: "http://localhost/model/ts-2068/" indiv: - name: "Robert Fischer" slug: "robert-fischer" taxonomy: "indiv" url: "http://localhost/indiv/robert-fischer/" publication: "SyncWare News" publication_r: id: 10245 title: "SyncWare News" type: "periodical" url: "http://localhost/periodical/syncware-news/" authors: "Robert C. Fischer" authors_r: - name: "Robert Fischer" slug: "robert-fischer" taxonomy: "indiv" url: "http://localhost/indiv/robert-fischer/" volume: "5" issue: "5" issues_articles: - id: 37720 title: "SyncWare News v5 n5" type: "issue" url: "http://localhost/issue/syncware-news-v5-n5/" pages: "8-10" pubdate: "May/June 1988" archive_link: false article_media: - id: 51164 title: "Machine Code Shell-Faulk Sort" type: "computer_media" url: "http://localhost/computer_media/machine-code-shell-faulk-sort/" --- # 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). ## Source Code: Machine Code Shell-Faulk Sort ``` 1 REM MACHINE CODE SHELL-FAULK SORT 5 REM SET UP RANDOM FILES X=NUMBER OF FILES N$(X+1,L) HOLDS ALL FILES PLUS ONE EXTRA FOR SHIFTING FILES 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 ```