Lightning Sort
Russ Gaspard
Last September COMPUTE! published "Ultrasort," and we called it the fastest sorting program ever published for any home computer. It would sort a 1000-element array in less than eight seconds.
It's been improved. Here's "Lightning Sort." It does the same thing in a breathtaking 2.1 seconds. Add this extraordinarily powerful subroutine to any of your BASIC programs where you need to alphabetize something. For the VIC, 64, and PC/PCjr. Atari users should refer to the accompanying sidebar and program "Bulldozer Sort."
The "Ultrasort" routine for Commodore computers (COMPUTE!, September 1983, p. 194) isn't as fast as it could be. After disassembling the code to study the algorithm, I found several opportunities to compact the code (mainly to reduce disk loading time) and to speed up the execution time. Using the "Sort Test" program from the original article as a benchmark, my "Lightning Sort" routine sorts a 1000-element array in an average of 2.1 seconds, versus 7.8 seconds for Ultrasort. That few seconds savings isn't much. But when I tried it on random 4000-element arrays the routine took an average of 10 seconds, versus 40 seconds for Ultrasort. A 400 percent speedup in execution time can be significant in applications where the sort routine is called repeatedly, or in sorting very large arrays.
The time for this type of algorithm to sort an N-element array is T*N*Log2N on the average, where T is about .21 milliseconds for the modified routine and .8 milliseconds for the original. Actual running time depends on the starting order of the array. Interestingly, whereas many sort algorithms run fastest when the original array is already in order, Hoare's Quicksort runs fastest on randomly ordered data. If you try it on an array which is already in correct order you'll find that it takes much longer (proportional to N2).
Besides speeding up the execution, I was also able to reduce the amount of RAM needed from 908 bytes to 418 bytes. By storing the variables in RAM space above the actual sorting routine rather than within the routine, the actual program storage needed on disk is only 338 bytes. This means the saved program uses only two disk blocks, rather than the four required for the original.
Program 1 is a BASIC program which loads the machine language Lightning Sort routine for the Commodore 64. The routine is loaded into RAM from $CO0O to $C152 (decimal 49152 to 49490), and writes variable data up to $C1A2 (decimal 49570). It is used in exactly the same way as Ultrasort. However, I prefer to define the call address 49152 as variable QS (either within the BASIC program or in direct mode) and then call the routine with:
SYS QS, N, AA$(K)
where K and N are the first element and the number of elements to sort, and AA$ is the array variable name, as in the Ultrasort article.
Program 2 is a BASIC loader for the VIC version of Lightning Sort. It automatically relocates the machine language to the top of available memory, regardless of the amount of expansion installed, and protects the sort routine from BASIC. The program also tells you the proper SYS to use to start the sorting.
Although Program 2 will run on an unexpanded VIC, we recommend that at least 8K expansion be used. With less than this, only a very few items can be sorted.
Program 3, the Sort Test program from the original Ultrasort article, can be used as a demonstration of Lightning Sort. The program creates an array, AA$, of 1000 random elements, then sorts them into order. If you are using a VIC with limited memory, you'll need to reduce the number of elements.
Program 1:
Lightning Sort Loader For The 64
Refer to the "Automatic Proofreader" article before typing this program in.
10 I = 49152 : SUM = 0 :rem 136 20 READ A: IF A = 256 THEN 40 :rem 54 30 SUM = SUM + A : POKE I, A : I = I + 1 : GOTO 20 :rem 79 40 IF SUM <> 45295 THENPRINT "ERROR IN DATA STATEMENTS"END :rem 191 50 PRINT"LIGHTNING SORT READY.":END :rem 214 49152 DATA 32, 253, 174, 32, 158, 173 :rem 52 49158 DATA 32, 247, 183, 165, 20, 133 :rem 52 49164 DATA 253, 165, 21, 133, 254, 32 :rem 46 49170 DATA 253, 174, 32, 158, 173, 162 :rem 104 49176 DATA 1, 165, 71, 157, 85, 193 :rem 221 49182 DATA 157, 125, 193, 165, 72, 157 :rem 114
Notes For Apple Version Of Lightning Sort
Tim Victor, Editorial Programmer
The Apple version of "Lightning Sort," shown in Programs 6 and 7, requires an Apple II with at least 48K of random access memory and one disk drive. It has been tested on an Apple II Plus under DOS 3.3 and on an Apple IIc under ProDOS as well as DOS 3.3. The Applesoft demonstration program in Program 7 uses the BLOAD command to load the file LIGHTNING.SORT. This is a binary file containing the Lightning Sort program that is entered from Program 6 using the Apple II's built-in ML monitor.
Boot your computer, then type "CALL — 151" to use the monitor. When you hit RETURN, the Applesoft input prompt will be replaced by an asterisk ("*"), the monitor's prompt. To enter a line from the listing, replace the hyphen after the first four-digit hexadecimal number with a colon. The first line in the listing would be entered as
9400: 20 B1 00 20 05 El A5 A0
Since no checksums are used in the listing, it's a good idea to make sure that the program in memory is correct. You can ask the monitor to display the contents of any memory location by typing its address as a hexadecimal number and hitting return. To examine a range of memory locations, type the address of the first location in the range, a period ("."), and then the address of the last location in the range. For example, Program 6 was made simply by entering "9400.9551" in response to the asterisk prompt.
When you're sure that the program is entered correctly, save it to disk using the BSAVE command. All DOS commands work in exactly the same way when entered from the monitor as when they are used in Applesoft. You can CATALOG, BLOAD, BSAVE, DELETE, and even LOAD and SAVE BASIC programs. To save the program you just entered, type "BSAVE LIGHTNING.SORT,A$9400,L$152" and hit RETURN. DOS will create a binary file named "LIGHTNING.SORT" and store in it $152 (338 in decimal notation) bytes beginning at memory location $9400 (decimal 37888).
Programmer's Notes: PC And PCjr Version
Tim Victor, Editorial Programmer
The PC and PCjr version of "Lightning Sort" (Program 4) is based on the same algorithm as the version for Commodore computers, but runs in about one-third the time, due to the greater speed and power of the 8088 microprocessor used in the IBM computers. There are a couple of differences in the way that this program is loaded and used.
The BASIC loader program calculates a checksum from the DATA statements to help identify typing errors, then creates a disk file named "LSORT.BAS", containing the ML routine in binary form. The demonstration (Program 5) loads this file into memory using BLOAD and sets LSORT to the address of the sort routine. This variable is needed because IBM BASIC'S CALL statement will only accept a variable name for the address of an ML routine.
Lightning Sort uses the first parameter in the CALL statement to find the array that it will sort. This is actually the address of the first string in the array, AA$(1) in the demonstration program, not the address of the array itself. The second parameter, N%, tells Lightning Sort how many strings are in the array. Variable names also have to be used for parameters, which is the reason for using N% instead of just plain 1000, and this version expects the length parameter to be an integer variable (a variable whose name ends with a percent sign).
Lightning Sort is loaded at address hex FF00 in BASIC'S default segment. During a sort, the 256 bytes starting at hex FE00 are also used. To protect this memory, both programs start with the instruction CLEAR, & HFE00, which sets the top of BASIC'S workspace to hex FE00.