QuickSort in 6502 assembler

[carlsson]

The first attempt failed, but after changing to a different algorithm, I got QuickSort working

Kind of. I was about to post the code, but I just found if the data to be sorted is too versatile (too big interval between smallest and largest) and at the same time already sorted, my algorithm recurses so many steps I run out of stack space and computer crashes. :-(

I tried to come up with a hackery solution, but so far I came up with no real good workaround. One way would be to take a copy of the whole stack elsewhere, and start a new one, but it is a bit clumsy. I tried to store only the low byte of the return address as long as I stay within the same memory page. It helped a bit, but not fully. Since the recursive calls come from only two places, maybe I can store some counter how many times the return address is valid instead of storing each return address:

Now: ret1 ret1 ret1 ret1 ret2 ret2 ret2 ret1 ret2 ret2 ret1 end (12 bytes)
Idea: 4 ret1 3 ret2 1 ret1 2 ret2 1 ret1 end (11 bytes)

I could probably align the code in a way so I can smart-code the counter into the return address or at least distinguish between the two, but I'd look for a general solution. This is nothing I need to use right now, so it is far from priority, just annoying.

Anyway, this is what I have for now. It would assemble with DASM and execute on a Commodore 64. Address $0400 equals screen matrix, so you can see the data being sorted.

#processor 6502
#seg main
 
array eqm $0400 ; $c100
larec eqm $c200
rarec eqm $c300
crec eqm $fa
ktmp eqm $fb
lval eqm $fc
left eqm $fd
right eqm $fe
 
          org $0900
 
          lda #$00
          sta crec
          tax
          sta larec,x
          lda #$ff
          sta rarec,x
          jsr quick
          rts
 
quick:    ldx crec
          lda rarec,x
          sta right 
          lda larec,x
          sta left
          inc crec
 
          tax                 ; left
          cpx right
          bcs qout$           ; if left >= right exit
          ldy right           
          lda array,y
          cmp array,x         ; if d[left] > d[right]
          bcs bprep$
          jsr swap
bprep$:   lda array,x         ; repeat
          sta lval
prep$:    lda lval
loop$:    cpx right
          beq loop2$
          inx
          cmp array,x         ;   repeat j=j+1 until d[left] <= d[j]
          beq loop2$
          bcs loop$
loop2$:   cpy left
          beq uloop2$
          dey
          cmp array,y         ;   repeat k=k-1 until d[left] >= d[k]
          bcc loop2$
uloop2$:  sty ktmp
          cpx ktmp            ;   if k >= j
          php
          bcs uloop1$
          jsr swap
uloop1$:  plp
          beq prep$
          bcc prep$
uprep$:   ldx left
          jsr swap
 
          ldx crec
          lda left
          sta larec,x
          cpy left
          php
          dey
          tya
          sta rarec,x
          plp
          bcc no1st$
          beq no1st$
          jsr quick           ; jsr
no1st$:   ldx crec
          ldy rarec,x
          iny
          iny
          tya
          sta larec,x
          lda rarec-1,x       ; lda right
          sta rarec,x
          jsr quick
qout$:    dec crec
          rts
 
;; swap takes x/y as index to the two values to swap
swap:     lda array,x
          pha
          lda array,y
          sta array,x
          pla
          sta array,y
          rts

To make it worse (?), I have another code written by someone else that is about the same in size, but functions better. It overcomes the recursive calls, which is something I'd like to do as well. I have some iterative implementation of QuickSort in a C book, but I never was successful to convert it into 6502. Maybe that's the desired approach anyway; stay away from recursion on small platforms.