Optimal Sort for any number of 16-bit elements by Mats Rosengren
[Up to Source Code Repository]

General Discussion

The extension of the "Optimal Sort" algorithm to "an unlimited number" (i.e. more then 255 elements) of 16 bit elements is straightforward using standard 6502 technique.

Consider first the loop using the Y register to sequentially access the elements starting with the second last and ending with the first in a sequence of up to 255 elements (note that the last access here is with 1 in the Y register, i.e. the "ZPADD" should point to the byte before the first element):

L1   DEY
     BEQ L3
     LDA (ZPADD),Y
     "some code"
     BRA L1
L3

L1   TYA
     BNE L2
     TXA
     BEQ L3
     DEX
     DEC ZPADD+1
L2   DEY
     LDA (ZPADD),Y
     "some code"
     BRA L1
L3

If initially the registers X and Y are given the values x and y and the value y is added to high part of the pointer ZPADD pointing to the first element of the sequence to be sorted the loop will be run through y + 256 * x times starting with the second last and ending with the first in a sequence of 1 + y + 256 * x elements. And when the loop is finished the pointer ZPADD will again point to the first element of the sequence while the X and the Y registers will take the value zero. Note that as here the last access is with 0 in the Y register the "ZPADD" should indeed point to the first element, not to the byte before the first element

To work with 16 bit values one has to handle the 8 less significant bits and the 8 more significant bits separately. The comparison is then made such that first the 8 most significant bits are compared. The 8 less significant bits only need to be compared if the 8 more significant bits were equal. The complete routine is then as follows:

SORT CLC
     LDA ZPADL+1        ;INITIALISE WORK4L
     ADC NVALH
     STA WORK4L
     BCS LER            ;BAD INPUT VALUES (TOO FAR TO BRANCH DIRECTLY)
     LDA ZPADH+1        ;INITIALISE WORK4H
     ADC NVALH
     STA WORK4H
LER  BCS L3B            ;BAD INPUT VALUES
L0   LDY NVALL          ;NUMBER OF DECREMENTS, LOW
     LDX NVALH          ;NUMBER OF DECREMENTS, HIGH
     LDA WORK4L
     STA ZPADL+1
     LDA (ZPADL),Y      ;LAST VALUE IN (WHAT IS LEFT OF) SEQUENCE TO BE SORTED
     STA WORK3L         ;SAVE LEAST SIGNIFICANT PART OF VALUE. WILL BE OVER-WRITTEN BY LARGEST NUMBER
     LDA WORK4H
     STA ZPADH+1
     LDA (ZPADH),Y      ;LAST VALUE IN (WHAT IS LEFT OF) SEQUENCE TO BE SORTED
     STA WORK3H         ;SAVE MOST SIGNIFICANT PART OF VALUE. WILL BE OVER-WRITTEN BY LARGEST NUMBER
     BRA L2
L1   TYA                ;START INNER LOOP
     BNE L1A
     TXA
     BEQ L3             ;EXIT INNER LOOP
     DEX
     DEC ZPADL+1
     DEC ZPADH+1
L1A  DEY
     LDA (ZPADH),Y
     CMP WORK2H
     BNE L1B
     LDA (ZPADL),Y
     CMP WORK2L
L1B  BCC L1
L2   LDA (ZPADL),Y
     STA WORK2L         ;POTENTIALLY LARGEST VALUE, LEAST SIGNIFICANT PART
     LDA (ZPADH),Y
     STA WORK2H         ;POTENTIALLY LARGEST VALUE, MOST SIGNIFICANT PART
     STY WORK1L         ;INDEX OF POTENTIALLY LARGEST VALUE, LOW
     LDA ZPADL+1
     STA WORK1LH        ;INDEX HIGH OF POTENTIALLY LARGEST VALUE, LEAST SIGNIFICANT PART
     LDA ZPADH+1
     STA WORK1HH        ;INDEX HIGH OF POTENTIALLY LARGEST VALUE, MOST SIGNIFICANT PART
     BRA L1             ;END INNER LOOP
L3   LDY NVALL          ;WHERE THE LARGEST VALUE SHALL BE PUT
     LDA WORK4L
     STA ZPADL+1
     LDA WORK2L         ;THE LARGEST VALUE, LEAST SIGNIFICANT PART
     STA (ZPADL),Y
     LDA WORK4H
     STA ZPADH+1
     LDA WORK2H         ;THE LARGEST VALUE, MOST SIGNIFICANT PART
     STA (ZPADH),Y
     LDY WORK1L         ;INDEX LOW OF FREE SPACE
     LDA WORK1LH        ;INDEX HIGH OF FREE SPACE, LEAST SIGNIFICANT PART
     STA ZPADL+1
     LDA WORK3L         ;THE OVER-WRITTEN VALUE, LEAST SIGNIFICANT PART
     STA (ZPADL),Y      ;PUT THE OVER-WRITTEN VALUE, LEAST SIGNIFICANT PART, IN THE FREE SPACE
     LDA WORK1HH        ;INDEX HIGH OF FREE SPACE, MOST SIGNIFICANT PART
     STA ZPADH+1
     LDA WORK3H         ;THE OVER-WRITTEN VALUE, MOST SIGNIFICANT PART
     STA (ZPADH),Y      ;PUT THE OVER-WRITTEN VALUE, MOST SIGNIFICANT PART, IN THE FREE SPACE
     LDA NVALL
     BNE L3A
     LDA NVALH
     BEQ L3B            ;EXIT OUTER LOOP
     DEC NVALH
     DEC WORK4L
     DEC WORK4H
L3A  DEC NVALL          ;END OF THE SHORTER SEQUENCE STILL LEFT
     BRA L0             ;START WORKING WITH THE SHORTER SEQUENCE
L3B  RTS

The calling program has to set the pointers ZPADL and ZPADH pointing to the start of the (separately stored) sequences of the 8 less and the 8 more significant bits of the values. The total number of values are 1 + y + 256 * x where the value x has to be given to variable NVALL and the value y has to be given to variable NVALH. At the end these variables will both be zero.

In addition the following 9 bytes are needed internally

WORK1L
WORK1LH
WORK1HH
WORK2L
WORK2H
WORK3L
WORK3H
WORK4L
WORK4H

;
ZPADL   = $30           ;2 BYTE POINTER IN PAGE ZERO TO THE "LESS SIGNIFICANT" SEQUENCE. SET BY CALLING PROGRAM
ZPADH   = $32           ;2 BYTE POINTER IN PAGE ZERO TO THE "MORE SIGNIFICANT" SEQUENCE. SET BY CALLING PROGRAM
NVALL   = $34           ;< "START ADDRESS" - "END ADDRESS" OF SEQUENCE. SET BY CALLING PROGRAM
NVALH   = $35           ;> "START ADDRESS" - "END ADDRESS" OF SEQUENCE. SET BY CALLING PROGRAM
;
;9 BYTES USED AS WORKING AREA
;
WORK1L  = $36           ;LOW INDEX (Y) FOR POTENTIALLY LARGEST VALUE
WORK1LH = $37           ;HIGH INDEX (ADDL+1) FOR POTENTIALLY LARGEST VALUE (LEAST SIGNIFICANT PART)
WORK1HH = $38           ;HIGH INDEX (ADDL+1) FOR POTENTIALLY LARGEST VALUE (MOST SIGNIFICANT PART)
WORK2L  = $39           ;POTENTIALLY LARGEST VALUE (LEAST SIGNIFICANT PART)
WORK2H  = $3A           ;POTENTIALLY LARGEST VALUE (MOST SIGNIFICANT PART)
WORK3L  = $3B           ;COPY OF LAST VALUE IN NOT YET SORTED SEQUENCE (LEAST SIGNIFICANT PART)
WORK3H  = $3C           ;COPY OF LAST VALUE IN NOT YET SORTED SEQUENCE (MOST SIGNIFICANT PART)
WORK4L  = $3D           ;HIGH ADDRESS FOR LAST ELEMENT IN NOT YET SORTED SEQUENCE (LEAST SIGNIFICANT PART)
WORK4H  = $3E           ;HIGH ADDRESS FOR LAST ELEMENT IN NOT YET SORTED SEQUENCE (MOST SIGNIFICANT PART)
     *=$1000            ;CODE ANYWHERE IN RAM OR ROM
     LDA #< SEQL
     STA ZPADL
     LDA #> SEQL
     STA ZPADL+1
     LDA #< SEQH
     STA ZPADH
     LDA #> SEQH
     STA ZPADH+1
     LDA #$09
     STA NVALL
     LDA #$00
     STA NVALH
     JSR SORT
     BRK
SEQL .BYTE    $30
     .BYTE    $20
     .BYTE    $DF
     .BYTE    $5A
     .BYTE    $81
     .BYTE    $C7
     .BYTE    $62
     .BYTE    $6D
     .BYTE    $6A
     .BYTE    $76
SEQH .BYTE    $05
     .BYTE    $1F
     .BYTE    $16
     .BYTE    $0D
     .BYTE    $1E
     .BYTE    $17
     .BYTE    $18
     .BYTE    $10
     .BYTE    $26
     .BYTE    $10
"Insert the code for subroutine SORT here"

To test the efficiency (and correctness) of this algorithm I generated a totally random permutation of the numbers 0 - 9999 using a random number generator. This sequence was successfully sorted using subroutine SORT above. I measured the number of T1H counts of the W65C22S timer 1 during this sorting, it was 4324613. As T1H decrements every 256 PHI2 pulses and my W6502 runs at 8 megahertz this corresponds to 138.4 seconds.

Last page update: April 20, 2004.