Posted By
Mad
on 2021-02-11
22:44:06
|  Re: sort algos for the 6502
I know it's off topic.. But if you want to sort a larger amount of entities (e.g. Sprites), lft has a good article about "field sort"..
It's actually just a longer list of iny commands where the opcodes are changed e.g. to jmp $c8c8 to collect the items on that position, so it collects all items one after the other.. It's a pretty cool trick and perhaps improvable by a simple hash collision scheme. But nevertheless it's not about sorting numbers, more about entities (e.g. by their screen position)..
It's actually some sort of a bucket sort, but very fast.
https://www.linusakesson.net/programming/fieldsort/index.php
If you do two passes of this sorting,as with any bucket sort,using 256 iny in this case, sorting first by the lowbyte and then sorting by the hibyte you could even sort 16 bit values..
|
