This is probably the fastest sorting program ever published for any home computer. It will alphabetize 1000 items in less than eight seconds.
    There are versions here for the 64, VIC, and 4.0 PET. You might want to change the amount sorted in the test program to reflect the available memory in your computer. If so, change N in line 110 o f Program 4. The test generates random "words" so you can see how the program works.

---

This article is a sequel to my earlier article "Super Shell Sort for PET/CBM" (February 1983). In that article, I described a shell sort program for the CBM 8032 written entirely in machine language. It performed as expected and was, overall, very fast; however, it had a couple of shortcomings. First of all, it had a rather clumsy interface with BASIC; that is, the calling sequence was not very neat; and second, sorting was performed by the shell sort algorithm. This method of sorting is actually quite efficient, certainly far better than a bubble sort, for instance. Nevertheless, there are better sorts.
    C.A.R. Hoare's Quicksort algorithm is possibly the fastest yet developed for most applications. So, I rewrote my machine language sort program based on the Quicksort algorithm.

Speed Improvements
How much better is it? In order to test the program, I wrote a small sort test program (Program 4), similar to the one in my original article. This program generates a character array containing N items (line 110).
    Different items are generated depending on the value of the random number seed, SD in line 140; SD must be a negative number.
    I generated six 1000 element arrays and sorted them using both the shell sort and Ultrasort. Super Shell Sort required an average of 29.60 seconds to sort all 1000 elements, while Ultrasort required an average of only 8.32 seconds. The sorting time has increased 72%. I don't believe you will find a faster sort for an eight-bit machine anywhere.
    The way you start the sort (see Program 4) has also been refined. To RUN the sort on the PET, you simply type:

    SYS 31744,N,AA$(K)

For the 64, use:

    SYS 49152,N,AA$(K)

The format is the same for the VIC, but the loader for the VIC version (Program 2) is designed to relocate itself to the top of available memory, which will vary according to the amount of expansion memory added to your VIC. (Ultrasort is too long for the unexpanded VIC.) The loader program will tell you the proper SYS address to use on your VIC.

RUNning The Program
Ultrasort can be used either from within a program or in immediate mode. RUNning Ultrasort causes N elements from array AA$, starting with element K, to be sorted into ascending order. The sort occurs in place; there is no additional memory overhead. N and K can be constants or variables, and any character array name can be substituted for AA$.
    Before RUNning the sort, though, it must be LOADed by BASIC. The appropriate loader is supplied in Programs 1-3. The tradeoff for the increased speed of Ultrasort is increased complexity, especially in machine language. The sort program runs from $7000 to $7F8B (908 bytes) on the PET. The increased size, of course, creates a greater possibility of errors when you enter the numbers. In order to minimize this, the PET loader (Program 1) is written to be self-checking to a degree. The DATA statements are grouped in blocks of 20 lines or 140 numbers (except for the first and last blocks), each of which is supplied with a checksum. If all the numbers in a block do not add up to the checksum, an error message is printed, giving you an indication of which block is in error. VIC and 64 owners should check their typing carefully, as there is no checksum.
    Notice that the first thing the loader programs do is reset the top of memory pointer. This is very important - you must use the BASIC loader before RUNning the sort program.
    Once Program 1 is loaded into upper memory of the PET, you should save it to disk by entering the monitor (SYS 4) and typing:

    S"0:ULTRASORT",08,7000,7F8C

VIC and 64 owners should use a monitor program or cartridge (e.g., VICMON, Supermon 64) or a routine such as "Machine Language Saver" (COMPUTE!, June 1983, p. 216) to save a copy of the Ultrasort machine language.
    To load your copy of Ultrasort from the PET monitor, reset the top of memory and type:

    L"0:ULTRASORT",08

From PET, VIC, or 64 BASIC type:

    LOAD"ULTRASORT",8,1  for disk, or
    LOAD"ULTRASORT",1,1  for tape.

    You can use Program 4 to watch the action with the PET, VIC, or 64 versions of Ultrasort.

Program 1: Ultrasort For PET

1 REM ULTRASORT-LOADER
10 POKE 52,0 : POKE 53,124 : CLR
20 FOR IB=1 TO 7
30 READ N,NL,CC:CS=0 : IF NL<>0 THEN L=NL
40 FORI=1 TO N : READ X : CS=CS+X : POKE
   L,X
50 L=L+1 : NEXT I
60 IF CS<>CC THEN PRINT"ERROR IN BLOCK"IB
    : END
70 PRINT"BLOCK"IB"OK"
80 NEXT IB
90 END
199 REM ... BLOCK 1 ...
200 DATA 3,31744,300
205 DATA 76,100,124
206 REM ... BLOCK 2 ...
207 DATA 140,31844,14808
210 DATA 32,245,190,32,152,189,32
215 DATA 45,201,165,17,141,12,124
220 DATA 165,18,141,13,124,32,245
225 DATA 190,32,152,189,56,165,68
230 DATA 233,3,133,84,165,69,233
235 DATA 0,133,85,162,1,173,12
240 DATA 124,157,20,124,173,13,124
245 DATA 157,40,124,169,1,157,60
250 DATA 124,169,0,157,80,124,189
255 DATA 60,124,141,16,124,189,80
260 DATA 124,141,17,124,189,20,124
265 DATA 141,18,124,189,40,124,141
270 DATA 19,124,32,47,127,173,11
275 DATA 124,48,4,202,208,221,96
280 DATA 189,60,124,141,16,124,189
285 DATA 80,124,141,17,124,169,1
290 DATA 141,18,124,169,0,141,19
295 DATA 124,32,101,127,189,20,124
300 DATA 141,18,124,141,14,124,189
305 DATA 40,124,141,19,124,141,15
306 REM ... BLOCK 3 ...
307 DATA 140,0,13385
310 DATA 124,32,47,127,173,11,124
315 DATA 48,3,76,167,125,32,131
320 DATA 127,173,16,124,141,3,124
325 DATA 173,17,124,141,4,124,173
330 DATA 14,124,141,5,124,173,15
335 DATA 124,141,6,124,32,132,126
340 DATA 32,180,126,173,11,124,48
345 DATA 218,173,16,124,141,3,124
350 DATA 173,17,124,141,4,124,173
355 DATA 18,124,141,16,124,173,19
360 DATA 124,141,17,124,169,1,141
365 DATA 18,124,169,0,141,19,124
370 DATA 32,101,127,173,16,124,141
375 DATA 18,124,173,17,124,141,19
380 DATA 124,173,3,124,141,16,124
385 DATA 173,4,124,141,17,124,32
390 DATA 47,127,173,11,124,16,35
395 DATA 173,14,124,141,3,124,173
400 DATA 15,124,141,4,124,173,18
405 DATA 124,141,5,124,173,19,124
406 REM ... BLOCK 4 ...
407 DATA 140,0,13499
410 DATA 141,6,124,32,132,,126,32
415 DATA 180,126,173,11,124,48,152
420 DATA 32,47,127,173,11,124,16
425 DATA 18,173,16,124,141,3,124
430 DATA 173,17,124,141,4,124,32
435 DATA 132,126,32,31,127,76,241
440 DATA 124,234,189,20,124,141,3
445 DATA 124,189,40,124,141,4,124
450 DATA 173,16,124,141,5,124,173
455 DATA 17,124,141,6,124,32,132
460 DATA 126,32,31,127,173,16,124
465 DATA 141,18,124,141,3,124,173
470 DATA 17,124,141,19,124,141,4
475 DATA 124,32,81,127,189,20,124
480 DATA 141,18,124,189,40,124,141
485 DATA 19,124,32,101,127,173,11
490 DATA 124,48,15,189,60,124,141
495 DATA 18,124,189,80,124,141,19
500 DATA 124,32,101,127,169,1,141
505 DATA 18,124,169,0,141,19,124
506 REM ... BLOCK 5 ...
507 DATA 140,0,15957
510 DATA 173,3,124,141,16,124,173
515 DATA 4,124,141,17,124,173,11
520 DATA 124,16,52,189,60,124,232
525 DATA 157,60,124,202,189,80,124
530 DATA 232,157,80,124,32,101,127
535 DATA 173,16,124,157,20,124,173
540 DATA 17,124,157,40,124,32,131
545 DATA 127,32,131,127,202,173,16
550 DATA 124,157,60,124,173,17,124
555 DATA 157,80,124,76,128,126,32
560 DATA 131,127,232,173,16,124,157
565 DATA 60,124,173,17,124,157,80
570 DATA 124,202,189,20,124,232,157
575 DATA 20,124,202,189,40,124,232
580 DATA 157,40,124,202,32,101,127
585 DATA 32,101,127,173,16,124,157
590 DATA 20,124,173,17,124,157,40
595 DATA 124,232,76,162,124,160,3
600 DATA 165,84,133,88,133,90,165
605 DATA 85,133,89,133,91,24,165
606 REM ... BLOCK 6 ...
607 DATA 140,0,15683
610 DATA 88,109,3,124,133,88,165
615 DATA 89,109,4,124,133,89,24
620 DATA 165,90,109,5,124,133,90
625 DATA 165,91,109,6,124,133,91
630 DATA 136,208,223,96,160,0,140
635 DATA 11,124,177,88,141,7,124
640 DATA 177,90,141,8,124,200,152
645 DATA 205,7,124,240,2,176,13
650 DATA 205,8,124,240,21,144,19
655 DATA 2.38,11,124,76,30,127,205
660 DATA 8,124,240,2,176,62,206
665 DATA 11,124,76,30,127,140,9
670 DATA 124,160,1,177,88,133,86
675 DATA 200,177,88,133,87,172,9
680 DATA 124,136,177,86,141,10,124
685 DATA 140,9,124,160,1,177,90
690 DATA 133,86,200,177,90,133,87
695 DATA 172,9,124,177,86,200,205
700 DATA 10,124,208,3,76,195,126
705 DATA 144,184,76,224,126,96,160
706 REM ... BLOCK 7 ...
707 DATA 108,0,11613
710 DATA 2,177,88,72,177,90,145
715 DATA 88,104,145,90,136,16,243
720 DATA 96,169,0,141,11,124,173
725 DATA 17,124,205,19,124,144,6
730 DATA 240,8,238,11,124,96,206
735 DATA 11,124,96,173,16,124,205
740 DATA 18,124,144,244,208,238,96
745 DATA 173,16,124,24,109,18,124
750 DATA 141,16,124,173,17,124,109
755 DATA 19,124,141,17,124,96,169
760 DATA 0,141,11,124,56,173,16
765 DATA 124,237,18,124,141,16,124
770 DATA 173,17,124,237,19,124,141
775 DATA 17,124,176,3,206,11,124
780 DATA 96,238,16,124,208,3,238
785 DATA 17,124,96

Program 2: Ultrasort For VIC

5 Il=PEEK(56)*256-1024
6 POKE 55,0:HI=INT(Il/256):POKE 56,HI:CL
  R
7 Il=PEEK(55)+PEEK(56)*256
8 HI=INT(I1/256)
10 I=I1
20 READ A:IF A=256 THEN PRINT"TO RUN SOR
   T, USE: SYS"Il:END
22 IF A<0 THEN A=ABS(A)-26+HI
25 IF A=257 THEN I=Il+100:GOTO 20
30 POKE I,A:I=I+1:GOTO 20
6656 DATA 76,100,-26,257
6768 DATA 32,253,206,32,158
6776 DATA 205,32,247,215,165,20,141
6784 DATA 12,-26,165,21,141,13,-26
6792 DATA 32,253,206,32,158,205,56
6800 DATA 165,71,233,3,133,75,165
6808 DATA 72,233,0,133,76,162,1
6816 DATA 173,12,-26,157,20,-26,173
6824 DATA 13,-26,157,40,-26,169,1
6832 DATA 157,60,-26,169,0,157,80
6840 DATA -26,189,60,-26,141,16,-26
6848 DATA 189,80,-26,141,17,-26,189
6856 DATA 20,-26,141,18,-26,189,40
6864 DATA -26,141,19,-26,32,47,-29
6872 DATA 173,11,-26,48,4,202,208
6880 DATA 221,96,189,60,-26,141,16
6888 DATA -26,189,80,-26,141,17,-26
6896 DATA 169,1,141,18,-26,169,0
6904 DATA 141,19,-26,32,101,-29,189
6912 DATA 20,-26,141,18,-26,141,14
6920 DATA -26,189,40,-26,141,19,-26
6928 DATA 141,15,-26,32,47,-29,173
6936 DATA 11,-26,48,3,76,167,-27
6944 DATA 32,131,-29,173,16,-26,141
6952 DATA 3,-26,173,17,-26,141,4
6960 DATA -26,173,14,-26,141,5,-26
6968 DATA 173,15,-26,141,6,-26,32
6976 DATA 132,-28,32,180,-28,173,11
6984 DATA -26,48,218,173,16,-26,141
6992 DATA 3,-26,173,17,-26,141,4
7000 DATA -26,173,18,-26,141,16,-26
7008 DATA 173,19,-26,141,17,-26,169
7016 DATA 1,141,18,-26,169,0,141
7024 DATA 19,-26,32,101,-29,173,16
7032 DATA -26,141,18,-26,173,17,-26
7040 DATA 141,19,-26,173,3,-26,141
7048 DATA 16,-26,173,4,-26,141,17
7056 DATA -26,32,47,-29,173,11,-26
7064 DATA 16,35,173,14,-26,141,3
7072 DATA -26,173,15,-26,141,4,-26
7080 DATA 173,18,-26,141,5,-26,173
7088 DATA 19,-26,141,6,-26,32,132
7096 DATA -28,32,180,-28,173,11,-26
7104 DATA 48,152,32,47,-29,173,11
7112 DATA -26,16,18,173,16,-26,141
7120 DATA 3,-26,173,17,-26,141,4
7128 DATA -26,32,132,-28,32,31,-29
7136 DATA 76,241,-26,234,189,20,-26
7144 DATA 141,3,-26,189,40,-26,141
7152 DATA 4,-26,173,16,-26,141,5
7160 DATA -26,173,17,-26,141,6,-26
7168 DATA 32,132,-28,32,31,-29,173
7176 DATA 16,-26,141,18,-26,141,3
7184 DATA -26,173,17,-26,141,19,-26
7192 DATA 141,4,-26,32,81,-29,189
7200 DATA 20,-26,141,18,-26,189,40
7208 DATA -26,141,19,-26,32,101,-29
7216 DATA 173,11,-26,48,15,189,60
7224 DATA -26,141,18,-26,189,80,-26
7232 DATA 141,19,-26,32,101,-29,169
7240 DATA 1,141,18,-26,169,0,141
7248 DATA 19,-26,173,3,-26,141,16
7256 DATA -26,173,4,-26,141,17,-26
7264 DATA 173,11,-26,16,52,189,60
7272 DATA -26,232,157,60,-26,202,189
7280 DATA 80,-26,232,157,80,-26,32
7288 DATA 101,-29,173,16,-26,157,20
7296 DATA -26,173,17,-26,157,40,-26
7304 DATA 32,131,-29,32,131,-29,202
7312 DATA 173,16,-26,157,60,-26,173
7320 DATA 17,-26,157,80,-26,76,128
7328 DATA -28,32,131,-29,232,173,16
7336 DATA -26,157,60,-26,173,17,-26
7344 DATA 157,80,-26,202,189,20,-26
7352 DATA 232,157,20,-26,202,189,40
7360 DATA -26,232,157,40,-26,202,32
7368 DATA 101,-29,32,101,-29,173,16
7376 DATA -26,157,20,-26,173,17,-26
7384 DATA 157,40,-26,232,76,162,-26
7392 DATA 160,3,165,75,133,79,133
7400 DATA 81,165,76,133,80,133,82
7408 DATA 24,165,79,109,3,-26,133
7416 DATA 79,165,80,109,4,-26,133
7424 DATA 80,24,165,81,109,5,-26
7432 DATA 133,81,165,82,109,6,-26
7440 DATA 133,82,136,208,223,96,160
7448 DATA 0,140,11,-26,177,79,141
7456 DATA 7,-26,177,81,141,8,-26
7464 DATA 200,152,205,7,-26,240,2
7472 DATA 176,13,205,8,-26,240,21
7480 DATA 144,19,238,11,-26,76,30
7488 DATA -29,205,8,-26,240,2,176
7496 DATA 62,206,11,-26,76,30,-29
7504 DATA 140,9,-26,160,1,177,79
7512 DATA 133,77,200,177,79,133,78
7520 DATA 172,9,-26,136,177,77,141
7528 DATA 10,-26,140,9,-26,160,1
7536 DATA 177,81,133,77,200,177,81
7544 DATA 133,78,172,9,-26,177,77
7552 DATA 200,205,10,-26,208,3,76
7560 DATA 195,-28,144,184,76,224,-28
7568 DATA 96,160,2,177,79,72,177
7576 DATA 81,145,79,104,145,81,136
7584 DATA 16,243,96,169,0,141,11
7592 DATA -26,173,17,-26,205,19,-26
7600 DATA 144,6,240,8,238,11,-26
7608 DATA 96,206,11,-26,96,173,16
7616 DATA -26,205,18,-26,144,244,208
7624 DATA 238,96,173,16,-26,24,109
7632 DATA 18,-26,141,16,-26,173,17
7640 DATA -26,109,19,-26,141,17,-26
7648 DATA 96,169,0,141,11,-26,56
7656 DATA 173,16,-26,237,18,-26,141
7664 DATA 16,-26,173,17,-26,237,19
7672 DATA -26,141,17,-26,176,3,206
7680 DATA 11,-26,96,238,16,-26,208
7688 DATA 3,238,17,-26,96,256

Program 3: Ultrasort For 64

10 I=49152
20 READ A:IF A=256 THEN END
30 POKE I,A:I=I+1:GOTO 20
49152 DATA 76,100,192,170,170,170,170
49159 DATA 170,170,170,170,170,170,170
49166 DATA 170,170,170,170,170,170,170
49173 DATA 170,170,170,170,170,170,170
49180 DATA 170,170,170,170,170,170,170
49187 DATA 170,170,170,170,170,170,170
49194 DATA 170,170,170,170,170,170,170
49201 DATA 170,170,170,170,170,170,170
49208 DATA 170,170,170,170,170,170,170
49215 DATA 170,170,170,170,170,170,170
49222 DATA 170,170,170,170,170,170,170
49229 DATA 170,170,170,170,170,170,170
49236 DATA 170,170,170,170,170,170,170
49243 DATA 170,170,170,170,170,170,170
49250 DATA 170,170,32,253,174,32,158
49257 DATA 173,32,247,183,165,20,141
49264 DATA 12,192,165,21,141,13,192
49271 DATA 32,253,174,32,158,173,56
49278 DATA 165,71,233,3,133,75,165
49285 DATA 72,233,0,133,76,162,1
49292 DATA 173,12,192,157,20,192,173
49299 DATA 13,192,157,40,192,169,1
49306 DATA 157,60,192,169,0,157,80
19313 DATA 192,189,60,192,141,16,192
49320 DATA 189,80,192,141,17,192,189
49327 DATA 20,192,141,18,192,189,40
49334 DATA 192,141,19,192,32,47,195
49341 DATA 173,11,192,48,4,202,208
49348 DATA 221,96,189,60,192,141,16
49355 DATA 192,189,80,192,141,17,192
49362 DATA 169,1,141,18,192,169,0
49369 DATA 141,19,192,32,101,195,189
49376 DATA 20,192,141,18,192,141,14
49383 DATA 192,189,40,192,141,19,192
49390 DATA 141,15,192,32,47,195,173
49397 DATA 11,192,48,3,76,167,193
49404 DATA 32,131,195,173,16,192,141
49411 DATA 3,192,173,17,192,141,4
49418 DATA 192,173,14,192,141,5,192
49425 DATA 173,15,192,141,6,192,32
49432 DATA 132,194,32,180,194,173,11
49439 DATA 192,48,218,173,16,192,141
49446 DATA 3,192,173,17,192,141,4
49453 DATA 192,173,18,192,141,16,192
49460 DATA 173,19,192,141,17,192,169
49467 DATA 1,141,18,192,169,0,141
49474 DATA 19,192,32,101,195,173,16
49481 DATA 192,141,18,192,173,17,192
49488 DATA 141,19,192,173,3,192,141
49495 DATA 16,192,173,4,192,141,17
49502 DATA 192,32,47,195,173,11,192
49509 DATA 16,35,173,14,192,141,3
49516 DATA 192,173,15,192,141,4,192
49523 DATA 173,18,192,141,5,192,173
49530 DATA 19,192,141,6,192,32,132
49537 DATA 194,32,180,194,173,11,192
49544 DATA 48,152,32,47,195,173,11
49551 DATA 192,16,18,173,16,192,141
49558 DATA 3,192,173,17,192,141,4
49565 DATA 192,32,132,194,32,31,195
49572 DATA 76,241,192,234,189,20,192
49579 DATA 141,3,192,189,40,192,141
49586 DATA 4,192,173,16,192,141,5
49593 DATA 192,173,17,192,141,6,192
49600 DATA 32,132,194,32,31,195,173
49607 DATA 16,192,141,18,192,141,3
49614 DATA 192,173,17,192,141,19,192
49621 DATA 141,4,192,32,81,195,189
49628 DATA 20,192,141,18,192,189,40
49635 DATA 192,141,19,192,32,101,195
49642 DATA 173,11,192,48,15,189,60
49649 DATA 192,141,18,192,189,80,192
49656 DATA 141,19,192,32,101,195,169
49663 DATA 1,141,18,192,169,0,141
49670 DATA 19,192,173,3,192,141,16
49677 DATA 192,173,4,192,141,17,192
49684 DATA 173,11,192,16,52,189,60
49691 DATA 192,232,157,60,192,202,189
49698 DATA 80,192,232,157,80,192,32
49705 DATA 101,195,173,16,192,157,20
49712 DATA 192,173,17,192,157,40,192
49719 DATA 32,131,195,32,131,195,202
49726 DATA 173,16,192,157,60,192,173
49733 DATA 17,192,157,80,192,76,128
49740 DATA 194,32,131,195,232,173,16
49747 DATA 192,157,60,192,173,17,192
49754 DATA 157,80,192,202,189,20,192
49761 DATA 232,157,20,192,202,189,40
49768 DATA 192,232,157,40,192,202,32
49775 DATA 101,195,32,101,195,173,16
49782 DATA 192,157,20,192,173,17,192
49789 DATA 157,40,192,232,76,162,192
49796 DATA 160,3,165,75,133,79,133
49803 DATA 81,165,76,133,80,133,82
49810 DATA 24,165,79,109,3,192,133
49817 DATA 79,165,80,109,4,192,133
49824 DATA 80,24,165,81,109,5,192
49831 DATA 133,81,165,82,109,6,192
49838 DATA 133,82,136,208,223,96,160
49845 DATA 0,140,11,192,177,79,141
49852 DATA 7,192,177,81,141,8,192
49859 DATA 200,152,205,7,192,240,2
49866 DATA 176,13,205,8,192,240,21
49873 DATA 144,19,238,11,192,76,30
49880 DATA 195,205,8,192,240,2,176
49887 DATA 62,206,11,192,76,30,195
49894 DATA 140,9,192,160,1,177,79
49901 DATA 133,77,200,177,79,133,78
49908 DATA 172,9,192,136,177,77,141
49915 DATA 10,192,140,9,192,160,1
49922 DATA 177,81,133,77,200,177,81
49929 DATA 133,78,172,9,192,177,77
49936 DATA 200,205,10,192,208,3,76
49943 DATA 195,194,144,184,76,224,194
49950 DATA 96,160,2,177,79,72,177
49957 DATA 81,145,79,104,145,81,136
49964 DATA 16,243,96,169,0,141,11
49971 DATA 192,173,17,192,205,19,192
49978 DATA 144,6,240,8,238,11,192
49985 DATA 96,206,11,192,96,173,16
49992 DATA 192,205,18,192,144,244,208
49999 DATA 238,96,173,16,192,24,109
50006 DATA 18,192,141,16,192,173,17
50013 DATA 192,109,19,192,141,17,192
50020 DATA 96,169,0,141,11,192,56
50027 DATA 173,16,192,237,18,192,141
50034 DATA 16,192,173,17,192,237,19
50041 DATA 192,141,17,192,176,3,206
50048 DATA 11,192,96,238,16,192,208
50055 DATA 3,238,17,192,96,170,170
50062 DATA 170,170,170,170,170,170,170
50069 DATA 170,170,170,170,170,170,170
50076 DATA 170,170,170,170,170,170,170
50083 DATA 170,170,170,170,170,170,170
50090 DATA 170,170,170,170,170,170,170
50097 DATA 170,170,170,170,170,170,170
50104 DATA 170,170,170,170,170,170,170
50111 DATA 170,170,170,170,170,81,85
50118 DATA 73,67,75,83,79,82,84
50125 DATA 32,76,79,65,42,32,32
50132 DATA 3,255,50,48,44,82,69
50139 DATA 65,68,32,69,82,82,79
50146 DATA 82,44,49,56,44,48,48
50153 DATA 0,170,170,170,170,81,85
50160 DATA 73,67,75,83,79,82,84
50167 DATA 32,76,79,65,68,69,82
50174 DATA 16,255,256

Program 4: Sort Test Program

100 PRINT "{CLR}"
110 N=1000
120 DIM AA$(N)
130 PRINT "CREATING"N" RANDOM STRINGS"
140 SD=-TI : A=RND(SD)
150 FOR I=1 TO N
160 PRINT I"(UP}"
170 Nl=INT(RND(1)*10+1)
180 A$=""
190 FOR J=1TO Nl
200 B$=CHR$(INT(RND(1)*26+65))
210 A$=A$+B$
220 NEXT J
230 AA$(I)=A$
240 NEXTI
250 PRINT "HIT ANY KEY TO START SORT"
260 GET A$:IF A$="" THEN 260
270 PRINT "SORTING..."
280 Tl=TI
290 REM SYS 31744,N,AA$(1) FOR PET/CBM
291 REM SYS 49154,N,AA$(1) FOR 64
292 REM USE SYS VALUE GENERATED BY THE
    LOADER FOR VIC
300 SYS 31744,N,AA$(1)
310 T2=TI
320 PRINT "DONE"
330 PRINT "HIT ANY KEY TO PRINT SORTED S
    TRINGS"
340 GET A$:IF A$="" THEN 340
350 FORI=1TON:PRINT I,AA$(I):NEXT
360 PRINT:PRINT N" ELEMENTS SORTED IN"(T
    2-T1)/60"SECONDS"

Special PET Version Note PETS with BASIC 4.0 do not have the problem of lengthy garbage collection times (this occurs when the computer finds that it has run out of memory, and must eliminate all strings that are no longer "active"). The price of this convenience is that all dynamic strings are now two bytes longer. Those two bytes are a "back-pointer" from the top of the memory (where the actual data contained in the string is kept) to the bottom of memory where the variable keeps a pointer to that data.     This sort does not modify the backpointers. So, if after sorting you continue using the new data, it will eventually be garbled.     There is a solution. Immediately after sorting, write the data to disk as a file. Then issue a CLR command. This will remove all your variables. Then read the data back off the disk into a new array.     This problem does not occur on the VIC-20 or the Commodore 64.