;pass1
	ldx sort+0
	ldy spry,x        ; get sprite y coord
	lax and#0fmul16,y ;get bucket startadress 
	ora bucket1+15,x  ;get adress INside the bucket
	inc bucket1+15,x  ;inc nr of elements
	tax		
smod	sty bucket1,x	  ;store spr to bucket



;pass2

	ldx bucket1+15
	beq next	;empty bucket dont bother
blp1	

	ldy bucket1,x
	lda spry,y         ;get spr y
	and #%11110000     ;upper 4 bits only this time
	tay                ;which is exactly our pointer
	ora bucket2+15,y   ;addy inside bucket
	inc bucket2+15,y   ;inc bucket counter
	tay                ;final bucket addy
	sta bucket2,y      ;store sprite
	dex
	bne blp1	   ;any more in bucket1?

next

;pass3
        ldy #$00 ; nr of sprites counter this is done only once

	ldx bucket2+15
	beq next             ;empty bucket?
blp2
	lda bucket2,x        ;get sprite nr
smod	sta final,y          ;store to final list
	iny                  ;final spr count
	dex           
	bne blp2             ;any more in curr. bucket?

	;; initialize the buckets
	ldx #$81
	!for i,0,16 {
	sta lsd_bucket+i
	}
	lda #$fe
	!for i,0,6 {
	sax msd_bucket+i*2+0
	stx msd_bucket+i*2+1
	sbx #-3
	}

	;; lsd sort
	lda #$0f
	!for i,0,32 {
	ldx actor_ypos+i
	sbx #$00
	ldy lsd_bucket,x
	sty actor_link+i
	ldy #i
	sty lsd_bucket,x
	}

	;; msd sort
	!for i,0,13 {
	ldx lsd_bucket+i
	bmi .next

.msd	ldy actor_ypos,x
	lda msd_table,y
	tay

	lda msd_bucket,y
	stx msd_bucket,y

	ldy actor_link,x
	sta actor_link,x
	bmi .next

	ldx actor_ypos,y
	lda msd_table,x
	tax

	lda msd_bucket,x
	sty msd_bucket,x

	ldx actor_link,y
	sta actor_link,y
	bne .msd

.next	}

	;; finally in the mux writer.
	;; for each sprite, alternating x and y
	ldx actor_link,y
	bpl .ok
.bucket	lda msd_bucket-$80,x
	tax
	bmi .bucket
.ok	...

;Fill Buckets
ldx input
inc Buckets,x
...
ldx input+31
inc Buckets,x
-------------
10*32=320 cycles assuming input is in ZP.

;Collect sorted values
ldy Buckets
beq next1:   ;Skip if empty.
lda #value1  ;Value corresponding to this bucket.       
pha
dey
bne *-2      ;In case not unique.
sty Buckets  ;Empty the buckets.
next1:
ldy Buckets+1
beq next2:
lda #value2
pha
dey
bne *-2
sty Buckets
next2:
;etc.

NOBJECTS  = 24	; Number of objects to be sorted

OBJ_YPOS  = $80	; Y-values of all objects
OBJ_SORT  = $A0	; Indices of all objects sorted by Y-value
TEMP_SP   = $FF	; Temporary stack pointer

StackSort:

	; Save stack pointer
	tsx		
	stx TEMP_SP

	; Phase 1 - Store Y-values in buckets
	.repeat NOBJECTS, i
	  lda OBJ_YPOS + i
	  ;lsr
	  tax
	  txs
	  pla
	  bpl *-1 ; Already value here, try next
	  lda #i
	  pha
	.endrep

	; Phase 2 - Gather (indices of) sorted values
	;ldx #(50/2)-1
	ldx #50-1
	txs
	.repeat NOBJECTS, i
	  pla
	  bmi *-1
	  sta OBJ_SORT + i
	  lda #$ff ; Clean up after ourselves
	  pha
	  pla
	.endrep

	; Restore stack pointer
	ldx TEMP_SP
	txs
	rts

	*=$10
clear_bucket_counter

	lda #0
	sta buckets+15
	sta buckets+15+16*1
	sta buckets+15+16*2
	sta buckets+15+16*3
	sta buckets+15+16*4
	sta buckets+15+16*5
	sta buckets+15+16*6
	sta buckets+15+16*7
	sta buckets+15+16*8
	sta buckets+15+16*9
	sta buckets+15+16*10
	sta buckets+15+16*11
	sta buckets+15+16*12
	sta buckets+15+16*13
	sta buckets+15+16*14
	sta buckets+15+16*15

	
	ldx #32
set_element_index
	stx element_index
	
	lda sprite_y,x
	ldx #$f0
	sbx #$00	;select right bucket

	ldy buckets+15,x	;get bucket counter (# elements in bucket)
	inc buckets+15,x	;increase bucket counter

	stx set_2+1	;set high nybble bucket index
	dey
	bmi place_current_element	;element count=0 skip sort
			
	stx get_1+1	
	stx get_2+1	
	inx
	stx set_1+1
	
			
	sty slot_hi+1	;highest index
	
compare_element_y
get_1	ldx buckets,y
	cmp sprite_y,x
	dey
	bcc insert_lower_element	;woohoo, found a spot
	bpl compare_element_y
	
insert_lower_element
	sty slot_lo+1	

slot_hi	ldy #0

move_higher_elements

get_2	lda buckets,y		;move higher elements up
set_1	sta buckets,y
	dey
slot_lo	cpy #$ff		
 	bcc move_higher_elements

place_current_element		;finally, insert the lower element index in the right place
	iny
	lax element_index
set_2	sta buckets,y
	dex
	bne set_element_index

	rts

element_index
	.byte 0	


	*=$1000
buckets
	.fill 256,0

.const	NSPRITES  	= 32
.const	indexes		= $60
.const	ypos		= $80

// SORT FORWARD
// ************
// Check if values are sorted, if necessary call sortbw routine to
// put an unsorted value in the correct position
sortfw:	
	.for(var i=0;i<NSPRITES;i++) {
		over:
			.if (i!=NSPRITES-1) {
				ldy indexes+1+i
				ldx indexes+i
				lda ypos,y
				cmp ypos,x
				bcs sortfw[i+1].over								
				jsr sortbw[NSPRITES-2-i].back				
			}
			else	rts			
	}

// SORT BACKWARD
// *************
// Move backward a value in .A which is less than the one in current position.
// All values at the left of the current position are ordered so, once we found
// the correct spot for .A, we don't need to check forward, we can get back
// to where the function was called
sortbw:
	.for(var i=0;i<NSPRITES-1;i++)	{
		back:
			stx indexes+NSPRITES-1-i
			.if (i!=NSPRITES-2) {
				ldx indexes+NSPRITES-3-i
				cmp ypos,x						
				bcc sortbw[i+1].back		
			}
			sty indexes+NSPRITES-2-i
			rts			
	}

.bucketK
bcc .nextBucket		;Branches always: decrease this value by 3 with selfmodifying code in phase 1 for every new sprite in the bucket.
lda #sprite_index	;index of last sprite
pha		
...	
lda #sprite_index  	;index of first sprite.
pha		
sty .bucketK+1	;Restore branch (to skip all sprites for empty buckets). Call with y=$1b for max 8 sprites per bucket. 

.nextBucket	;unrolled
-------------
3 cycles for an empty bucket, 12 voor buckets with 1 sprite => 3*(220-32)+12*32 = 948 cycli 

dex   ;counts sprite index. Initialized with $20.
bmi .phase2
lda Yvalues,x   
asl
bcs *+8   ;There are more than 128 buckets, so I use 2 jump tables
sta *+4
jmp ($xxxx) ;jump table for buckets <128	;jumps to code that fills out phase2 Bucket code (see below)
sta *+4
jmp ($xxxx) ;jump table for buckets >=128	;21/22 cycles sofar
.phase2
clc	;to branch always (either to next bucket or to fetch the sprite indices in the current bucket).
ldy #27		;to restore the branch value of the bucket
jmp .Bucket0
           

;code to fill out bucketK
ldy .bucketK+1   ;The trick is that I use this as an index for the number of sprites already in the bucket
lda newBranchValue,y		;fetch value to branch to the code for one more sprite 
sta .bucketK+1   ;since this is unrolled code, the address of .bucketK is known
tay
txa
sta .bucketK+3,y  ;Store new sprite index. This works since the branch value decreases by 3 for each new sprite, but the address where to store the sprite index as well!
...	;Unrolled => repeat all the above code starting with dex.
--------------
41/42 cycles ->41.5*32 = 1328

newBranchValue
 BYTE 0 x x 0 x x 3 x x 6 x x 9 x x 12 x x 15 x x 18 x x x x x 21 x 

.bucketK
bcc .nextBucket
lda #K
pha
lda #K
pha
...
pha
sty .BucketK+1

ldy .bucketK+1 
lda newBranchValue,y		
sta .bucketK+1

.hitableN
  sta *+4
  jmp ($xxxx) ;jump table for buckets >=128
.phase2N
  clc	                ;to branch always.
  ldy #27	   	;to restore the branch value of the bucket
  jmp .Bucket0

for i in 0..73:
    .byt 64+(i%74)*(1+i//74*24)%74)

    ;code to fill out bucketK.   24 bytes, 36 cycles
fillK
    ldy .bucketK+1
    lda newBranchValue,y
    sta .bucketK+1         ; 12
    tay
    txa
    sta .bucketK+3,y       ;  9

    dex
    lda Yvalues,x
    sta *+4
    jmp ($xxxx)            ; 15

    ; 36*32 =  1152 cycle, 36 per actor

.bucketK ;32 bytes
    bcc .nextBucket        ;Branches always: decrease this value by 3 with selfmodifying code in phase 1 for every new sprite in the bucket.
    !byt 0,0,0
    lda #sprite_index   ; repeat lda/pha eight times
    pha
...
    sty .bucketK+1    ;Restore branch (to skip all sprites for empty buckets). Call with y=$1e for max 8 sprites per bucket.
.nextBucket    ;unrolled

    ; 3 cycles for an empty bucket, 12 voor buckets with 1 sprite => 3*(220-32)+12*32 = 948 cycli , 29.6 per actor

.bucketK
bcc .nextBucket
lda #sprite_index8
pha
...
nop
nop
nop
lda #sprite_index1
pha
sty .bucketK+1

ldy .bucketK+1
lda newBranchValue,y
sta .bucketK+1
txa
sta .bucketK,y

newBranchValue
 BYTE 0 x x 0 x x 3 x x 6 x x 9 x x 12 x x 15 x x 18 x x 21 x x x x x 27 x

for i in 0..73:
    .byt 64+(i%74)*(1+i//74*24)%74)

for i in 0..73:
    .byt 64+(i*1)%74

for i in 0..73:
    .byt 64+(i*25)%74

for i in 0..73:
    .byt 64+(i*49)%74

ldy .bucketK+1
ldx newBranchValue,y
stx .bucketK+1
sta .bucketK+3,x
sbc #$01
.start
tax
ldy Yvalues,x
sty *+4
jmp ($xxxx)

lax .bucketK+1
sbx #$06
stx .bucketK+1
tya
sta .bucketK+3,x
dey
lda Yvalues,y
sta *+4
jmp ($xxxx)

bcc .nextBucket
lda #sprite_index
pha
skw $abcd          ;opcode $0c
lda #sprite_index  ;Always 6 bytes for every sprite.
pha                ;Therefore sbx #$06 can be used in the fill routines.
skw $abcd
...
lda #sprite_index
pha
sty .bucketK+1

    ldx bucketK+1
    ldy newBranchTableValue,x
    sty bucketK+1
    pla ; grab this actor's index
    sta bucketK+3,y       ;21

    pla ; grab next Yvalue
    sta *+4
    jmp (jumptable)       ;11

SHX $FE00,Y

.C:fb52  A4 90       LDY $90+0     ; Y coordinate of actor 0
.C:fb54  9E 00 FE    SHX $FE00,Y   ; this is effectively STX $fe00,y
.C:fb57  B9 00 AA    LDA $AA00,Y   ; bucket head
.C:fb5a  85 10       STA $10+0     ; next pointer for actor 0
.C:fb5c  A9 00       LDA #$00      ; actor id 0
.C:fb5e  99 00 AA    STA $AA00,Y

.C:4c4c  8C 5E 4C    STY $4C5E     ; patch return address
.C:4c4f  BF 00 AA    LAX $AA00,Y   ; fetch bucket head
.C:4c52  48          PHA
.C:4c53  B5 10       LDA $10,X     ; read 'next' pointer.
.C:4c55  10 FA       BPL $4C51     ; Actor ids are positive, INY is not
.C:4c57  99 00 FE    STA $FE00,Y   ; restore INY
.C:4c5a  99 00 AA    STA $AA00,Y   ; empty linked list
.C:4c5d  4C 7E FE    JMP $FE7E

for each actor i
   ldx ypos+i
   inc count,x

   lda #0
   clc
for each count k
   sta start+k
   adc count+k

for each actor i
   ldx ypos+i
   ldy start,x
   lda #i
   sta output,y
   inc start,x
   lda #0
   sta count,x

irq:
	sty $ff+stack	// Fix stack for RTI
	lda buckethead,y
irqloop:	
	sta output,x
	tay
	inx
	lda list,y
	bpl irqloop
	ldy $ff+stack
	sta table,y
	sta sectable,y
	rti	

   ldx #offset
for SPRITE = 0 to n-1
   dcp (ypos(SPRITE),x)  ;operand byte is also memory for ypos
next
   lda #$ff
   ldx #$00
for LINE = 0 to 2*(floor((k/2)-2)) STEP 2
   stx start+LINE
   sbx #$00              ;operand byte is memory for the count-array
next
   stx start+2*(floor((k/2)-1))
for SPRITE = 0 to n-1
   ldx ypos(SPRITE)
   ldy start,x
   lda #SPRITE
   sta output,y
   inc start,x
   lda #0
   sta (offset,x)
next

   ...
Sprite0_ypos = *+1
   dcp (ypos(Sprite0),x)
Sprite1_ypos = *+1
   dcp (ypos(Sprite1),x)
   ...

   lda #$ff
   ldx #$00
   stx start+0
count_ypos0 = *+1
   sbx #$00
   stx start+2
count_ypos2 = *+1
   sbx #$00
   stx start+4
   ...

ypos0 .byte <count_ypos0, >count_ypos0
ypos2 .byte <count_ypos2, >count_ypos2
...

; YSortPositions contains the reduced spritepositions in Y
NUMBEROFBYTESTOBESORTED = 32
; With tables on zero-page
; 2 + ((3 + 9 + 6 + 19) * NUMBEROFBYTESTOBESORTED) - 3 + 2 + 3 + 12 = 1200

; With tables not on zero-page
; 2 + ((4 + 11 + 8 + 22) * NUMBEROFBYTESTOBESORTED) - 4 + 2 + 3 + 12 = 1455

DoSort
	lda #0				;  2
.for i = 0, i < NUMBEROFBYTESTOBESORTED, i = i + 1
	sta SortTable + i		;  4 /  3
.next
.for i = 0, i < NUMBEROFBYTESTOBESORTED, i = i + 1
	ldx YSortPositions + i		;  4 /  3
	inc YSortPositions,x		;  7 /  6
					;--------
					; 11 /  9
.next
	clc				;  2
.for i = 0, i < NUMBEROFBYTESTOBESORTED, i = i + 1
	sta SortOrder + i		;  4 /  3
	.if i < (NUMBEROFBYTESTOBESORTED - 1)
		adc SortTable + i	;  4 /  3
	.fi
					;--------
					;  8 / 6
.next
.for i = 0, i < NUMBEROFBYTESTOBESORTED, i = i + 1
	ldx ySortPos + i		;  4 /  3
	ldy SortOrder,x			;  4
	inc SortOrder,x			;  7 /  6
	lda #i				;  2
	sta Sorted,y			;  5 /  4
					;--------
					; 22 / 19
.next
	rts				; 12 (jsr + rts)

DoSort
    lda #0
.for i = 0, i < NUMBEROFBYTESTOBESORTED, i = i + 1
    sta SortTable + 8*i
.next
    lda #$f8
.for i = 0, i < NUMBEROFBYTESTOBESORTED, i = i + 1
    ldx YSortPositions + i
    sbx #0
    inc SortTable,x
.next
...

        sty     endptr+1
        lax     ylink,y
        pha
        lda     actorlink,x
        sta     ylink,y
        bpl     endptr

        sta     inyfield,y
endptr  jmp     inyfield

#Fibonacci Sort
unsorted = [3, 1, 4, 1, 5, 9, 2, 6, 0]
counts = [0] * 10
fib    = [0] * (10 + 1)
sortd    = [0] * len(unsorted)

#First pass: find the counts
for n in unsorted:
    counts[n]+=1

#Second pass: do the Fibonacci magic
i = 0
total = 0
for n in counts:
    fib[i] = total
    total += n
    i+=1
    
#Third pass: output sorted
for n in unsorted:
    sortd[fib[n]] = n
    fib[n] += 1

#Results
print(sortd)

;count each number
ldx #$ff
count ldy unsort,x
inc count,y
dex
bne count;15/ea

;Fibonacci step
clc
lda count
inx
fib adc count,x
sta sta count,x
inx
bne fib;13/ea

;Copy sorted
sort ldy unsort
ldx count,y
sty sort,x
inc count,y
inc sort+1
bne sort/27/ea

            // Radix sort of 32 "actors" based on their y-positions [0,223] in ascending order
            //
            // Worst case execution time: 2044 cycles
            //
            // 1248 bytes of code
            // 62 bytes of zeropage (in addition to y-positions)

            // * = $xx85 for no branch page boundary crossings
                
.const NUM_SPRITES = 32
.const NUM_LSD_BUCKETS = 16
.const NUM_MSD_BUCKETS = 14

            // Init
            // Constant 92 cycles

            lda #$ff            // 2 cycles
.for (var i = 0; i < NUM_LSD_BUCKETS; i++)
            sta lsd_buckets + i // 3        
.for (var i = 0; i < NUM_MSD_BUCKETS; i++)
            sta msd_buckets + 8*i // 3

            // LSD sort
            // Constant 576 cycles

            lda #NUM_LSD_BUCKETS - 1 // 2
.for (var i = 0; i < NUM_SPRITES; i++)
{
            ldx ypos + i        // 3
            axs #$00            // 2
            ldy lsd_buckets,x   // 4
            sty links + i       // 3

    .if (i == NUM_LSD_BUCKETS - 1)
            sta lsd_buckets,x   // 4
    else
    {
            ldy #i              // 2
            sty lsd_buckets,x   // 4
    }
}

            // MSD sort
            //
            // Execution time per LSD list as a function of number of list elements:
            // - 0 elements:        6 cycles
            // - N (odd) elements:  5 + (N - 1) / 2 * (26 + 28) + 27 cycles
            // - N (even) elements: 5 + (N - 2) / 2 * (26 + 28) + 26 + 27 cycles
            //
            // Worst case 958 cycles (15 empty LSD lists, 1 32-element LSD list)

.for (var i = 0; i < NUM_LSD_BUCKETS; i++)
{
            ldx lsd_buckets + i // 3
            bmi NextBucket      // 2/3
Next:       
            lda ypos,x          // 4
            alr #$f0            // 2
            tay                 // 2
            lda msd_buckets,y   // 4
            stx msd_buckets,y   // 4
            ldy links,x         // 4
            sta links,x         // 4
            bmi NextBucket      // 2/3

            lda ypos,y          // 4
            alr #$f0            // 2
            tax                 // 2
            lda msd_buckets,x   // 4
            sty msd_buckets,x   // 4
            ldx links,y         // 4
            sta links,y         // 5 !!!
            bpl Next            // 2/3
NextBucket:
}

            // Output final sorted order
            //
            // Execution time per MSD list as a function of number of list elements:
            // - 0 elements:        6 cycles
            // - N (odd) elements:  5 + (N - 1) / 2 * 21 + 10 cycles
            // - N (even) elements: 5 + (N - 2) / 2 * 21 + 20 cycles
            //
            // Worst case 418 cycles (13 empty MSD lists, 1 32-element MSD list)

.for (var i = NUM_MSD_BUCKETS - 1; i >= 0; i--)
{
            lax msd_buckets + 8*i // 3
            bmi NextBucket      // 2/3
Next:       
            pha                 // 3    
            lda links,x         // 4
            bmi NextBucket      // 2/3              

            pha                 // 3
            tay                 // 2
            lax links,y         // 4
            bpl Next            // 2/3
NextBucket:
}               

            stx msd_buckets,y   // 4

.const NUM_SPRITES = 32
.const NUM_LSD_BUCKETS = 16
.const NUM_MSD_BUCKETS = 14

         * = $10 "Zeropage data" virtual         
       
// Actor y positions in [0,223]
ypos:
.fill NUM_SPRITES,0

// Head of linked list per LSD bucket.
lsd_buckets:
.fill NUM_LSD_BUCKETS, 0

// Next "pointer" in (LSD or MSD) bucket list.
links:
.fill NUM_SPRITES, 0

// Head of linked list per MSD bucket.
msd_buckets:
.fill NUM_MSD_BUCKETS * 8, 0


Memory Map
----------
Default-segment:
  *$0010-$00cf Zeropage data

+---------------+------------------+---------+--------+-----------+------+
| author        | algorithm        |  worst  | code+  | zeropage  | year | 
|               |                  | cycles  | data   |           |      | 
+---------------+------------------+---------+--------+-----------+------+
| cjam          | flagged buckets  |   2422  |  ~3kb  |   59b     | 2017 | 
| lft           | field sort       |   2200  | sparse |   64b     | 2017 | 
| colorbar+cjam | inline buckets   |   2086  |  19kb  |    0b     | 2017 | 
| bezerk        | radix            |   2044  |  ~2kb  |   94/185b | 2020 | 
| bezerk+lft    | radix            |   1970  |  ~2kb  |   32b     | 2020 | 
+---------------+------------------+---------+--------+-----------+------+

sprite_sorty    ldy sorted_indexz+1                     ; first iteration only compares element 0 & 1 in the table, so no loop needed
                lda object_yl,y          ; y position of object in position 1                         
                ldx sorted_indexz                       ; get pointer to the object in position 0
                cmp object_yl,x          ; compare y position of object 0 to y position of object 1 (stored in AR)
                bcs @second                             ; if Obj 1 > Obj 0 we are done                                        
                stx sorted_indexz+1                     ; otherwise swap them       
                sty sorted_indexz     
                 
@second         ldx #2                                  ; get first position to be compared
@loop           stx current_pos                         ; position in index table we are finding the right place for  

                ldy sorted_indexz,x                     ; get pointer (offset) to current object to find the right place for
                sty current_index                       ; store current index number dynamically in code for later storage                
                lda object_yl,y          ; y position of current object into AR             
                
@in_right_place ldy sorted_indexz-1,x                   ; check if object is already in the right place ... saves time if list is already partially sorted 
                cmp object_yl,y          ; ... if it is we dont need to swap any positions but can move right on
                bcs @next_position                    
                sty sorted_indexz,x                      
                dex 
                
@compare        ldy sorted_indexz-1,x                   ; get pointer to the object we are comparing current one with
                cmp object_yl,y          ; compare y position of this object to y position of current object (stored in AR)
                bcs @found_place                        ; is y of current object (in AR) >= y of compare object
                sty sorted_indexz,x                     ; move the compared to index one right in the table             
                dex                                     ; loop to check next position
                bne @compare
                
@found_place    lda current_index                       ; index to current object
                sta sorted_indexz,x                     ; store to the right of the one it is >= of

                ldx current_pos
@next_position  inx
                cpx #NUM_SPR_OBJ                        ; end of table (number of sprite objects)?
                bcc @loop
                                       
@end            rts

@loop           sty current_pos                         ; position in the index 
                lda (sorted_indexz),y                   ; y coordinate of object  
                ldx sorted_indexz,y                     ; object number/index 
                stx current_index
                
@in_right_place cmp (sorted_indexz-2),y                 ; compare to y coordinate of next object in index                      
                bcs @next_position
                ldx sorted_indexz-2,y                   ; move compared objects index to the right sorted index list  
                stx sorted_indexz,y
                dey
                dey 
                
@compare        cmp (sorted_indexz-2),y                 
                bcs @found_place 
                ldx sorted_indexz-2,y
                stx sorted_indexz,y
                            
                dey
                dey 
                bne @compare 

@found_place    ldx current_index 
                stx sorted_indexz,y

@next_position  ldy current_pos
                iny
                iny
                cpy #2*NUM_SPR_OBJ
                bcc @loop