* Shell-Metzner Sort (133 bytes)
* based on 65816 instructions - but 6502 sort (187 bytes) available on request
* The only caveat is that all strings or numbers have to be the same length
* totally relocatable within bank #0 in the first 64kb of mem
* uses zero-page, not Direct page
* this sort is good for sorting dates (YY/MM/DD), variables & addresses of fixed length
* but will take a little more programming to modify for strings of varying lengths
Code:
* Enter these 5 entries before calling
STRLEN = $00 ; length of strings
STRTPOSN = $02 ; start position in string
NUMCHARS = $04 ; # of chars to compare
NUMENTRY = $06 ; # of words in list
STRTMEM = $08 ; starting address of word list
ENDPOSN = $0A
INTERMED = $0C
LO_CNT = $E0
HI_CNT = $E2
FVAR = $E4
PVAR = $E6
LO_PTR = $E8
HI_PTR = $EA
ORG ???? ; did I mention it is totally relocatable?
CLC
XCE
REP #$30
CLC
LDA STRTPOSN
ADC NUMCHARS
STA ENDPOSN
LDA NUMENTRY ; I=N
STA INTERMED
L200F LSR INTERMED ; I=INT (I/2)
BNE L201D
RTS
* always start comparing with word at midpoint
L201D SEC
LDA NUMENTRY ; # of entries
SBC INTERMED
STA FVAR ; F = N - I
LDA #0
L2034 STA PVAR : P=P+1
L2038 STA LO_CNT ; L=P
* get half-way point
CLC ; H=L+I
ADC INTERMED ; add half way point
STA HI_CNT : Hi counter
* this is a multiply by max # of chars in string
LDA #0
LDY STRLEN
BEQ ADDLO
]LP ADC LO_CNT
DEY
BNE ]LP ; always
ADDLO ADC STRTMEM
STA LO_PTR
LDA #0
LDY STRLEN
BEQ ADDHI
]LP ADC HI_CNT
DEY
BNE ]LP ; always
ADDHI ADC STRTMEM
STA HI_PTR
COMPARE SEP #$30
LDY STRTPOSN
]LP LDA (HI_PTR),Y ; is STR$(H)<STR$(L)?
CMP (LO_PTR),Y
BCC L209B ; yes, go swap
BNE L20C3 ; no, but they are also not the same
INY
CPY ENDPOSN ; last position to check
BNE ]LP
L20C3 LDA PVAR ; P=P+1
INC
CMP FVAR : is P>F
BCC L2034 ; no, goto STA Pvar : STA LO
BEQ L2034 ; no, goto STA Pvar : STA LO
BNE L200F ; yes, goto I=I/2
*Swap strings
L209B LDY STRLEN ; Y= max string length
DEY ; make from 1- to 0-
]LP LDA (LO_PTR),Y
TAX
LDA (HI_PTR),Y
STA (LO_PTR),Y
TXA
STA (HI_PTR),Y
DEY
BPL ]LP
REP #$30
NEXT SEC
LDA LO_CNT ; L=L-I
SBC INTERMED ; INTERMEDIATE
BMI L20C3 ; if <0 goto P=P+1
BNE L2038 ; if >0 goto STA LO_CNT: H=L+I
BRA L20C3 ; if =0 goto P=P+1