Originally posted by carlsson View Post
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
          sta larec,x
          lda #$ff
          sta rarec,x
          jsr quick
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$
          cmp array,x         ;   repeat j=j+1 until d[left] <= d[j]
          beq loop2$
          bcs loop$
loop2$:   cpy left
          beq uloop2$
          cmp array,y         ;   repeat k=k-1 until d[left] >= d[k]
          bcc loop2$
uloop2$:  sty ktmp
          cpx ktmp            ;   if k >= j
          bcs uloop1$
          jsr swap
uloop1$:  plp
          beq prep$
          bcc prep$
uprep$:   ldx left
          jsr swap
          ldx crec
          lda left
          sta larec,x
          cpy left
          sta rarec,x
          bcc no1st$
          beq no1st$
          jsr quick           ; jsr
no1st$:   ldx crec
          ldy rarec,x
          sta larec,x
          lda rarec-1,x       ; lda right
          sta rarec,x
          jsr quick
qout$:    dec crec
;; swap takes x/y as index to the two values to swap
swap:     lda array,x
          lda array,y
          sta array,x
          sta array,y
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.