Software - Sort - Counting sort

Small array (<= 256 bytes) version

TEMP is a 256 byte temporary buffer

Enter with:

• BUFFER = address of buffer of bytes to be sorted
• Y = number of bytes (in BUFFER) to sort - 1

TEMP DS 256       ; temporary storage

SORT
   LDA #0         ; clear counters
   TAX
.1 STA TEMP,X
   INX
   BNE .1

   TYA
   BEQ .3         ; branch if this is the last element
.2 LDA (BUFFER),Y ; count how many of each value there are
   TAX
   DEC TEMP,X
   DEY
   BNE .2
.3 LDA (BUFFER),Y ; handle last element specially
   TAX
   DEC TEMP,X

   CLC            ; write the values in numerical order
   LDX #0
.4 LDY TEMP,X
   BEQ .6
   TXA
.5 DEY
   STA (BUFFER),Y ; STA doesn't affect the Z flag!
   BNE .5
   LDA TEMP,X     ; BUFFER = BUFFER + TEMP,X
   ADC BUFFER     ; only ADC and CLC affect the carry in this section
   STA BUFFER
   BCC .6
   INC BUFFER+1
   CLC
.6 INX
   BNE .4
   RTS

Large array (> 256 bytes) version

Enter with:

• BUFFER = address of buffer of bytes to be sorted
• LAST = number of bytes (in BUFFER) to sort - 1

LASTL DS 1             ; parameter
LASTH DS 1             ; "
BUFH  DS 1             ; temporary storage
TEMP  DS 512           ; "

SORT
   LDA #0              ; clear the counters
   TAY
.1 STA TEMP,Y
   STA TEMP+256,Y
   INY
   BNE .1

   LDA BUFFERSTART+1   ; save the high byte of the buffer pointer
   STA BUFH

   LDA LASTH           ; count how many of each value there are
   BEQ .4
.2 LDA (BUFFERSTART),Y ; count a page (256 elements) at a time
   TAX
   INC TEMP,X
   BNE .3
   INC TEMP+256,X
.3 INY
   BNE .2
   INC BUFFERSTART+1
   DEC LASTH
   BNE .2
.4 LDY LASTL
   BEQ .7
.5 LDA (BUFFERSTART),Y ; count what's left
   TAX
   INC TEMP,X
   BNE .6
   INC TEMP+256,X
.6 DEY
   BNE .5
.7 LDA (BUFFERSTART),Y ; handle Y=0 separately
   TAX
   INC TEMP,X
   BNE .8
   INC TEMP+256,X

.8 LDA BUFH            ; restore the high byte of the buffer pointer
   STA BUFFERSTART+1

   CLC
   LDX #0              ; store the values in numerical order
.9 LDA TEMP+256,X
   BEQ .B
   TXA
.A STA (BUFFERSTART),Y ; store a page at a time
   INY
   BNE .A
   INC BUFFERSTART+1   ; update the high byte of BUFFERSTART
   DEC TEMP+256,X      ; decrement the high byte of the count
   BNE .A
.B LDY TEMP,X
   BEQ .D
   TXA                 ; necessary when the BEQ .B above was taken
.C DEY                 ; store what's left
   STA (BUFFERSTART),Y ; STA doesn't affect the Z flag!
   BNE .C
   LDA TEMP,X          ; BUFFERSTART = BUFFERSTART + TEMP,X
   ADC BUFFERSTART     ; only ADC & CLC affect the carry in this section
   STA BUFFERSTART
   BCC .D
   INC BUFFERSTART+1
   CLC
.D INX
   BNE .9
   RTS