Posted By
Litwr
on 2021-02-12
02:54:02
|  Re: sort algos for the 6502
Thank you for this link. Indeed the bucket/radix sorts are fast but they have several drawbacks:
1) they require memory for a copy of sorted array - we don't need such copy only if we sort little values like bytes, 4-bit nibbles, etc;
2) they need an additional array, for example the radix-8 sort requires 512 bytes for such an array;
3) if we need to sort long multi-byte values we need to do several passes and this slows down sorting, for example the radix/bucket sorts are faster on 32-bit integers on a modern computer but it is slower than quicksort on 128-bit integers;
4) they are difficult to adapt to various types of data.
A man claimed that he implemented a general bucket/radix kind sort for the 6502 - http://forum.6502.org/viewtopic.php?f=2&t=4228#p48897 - but I didn't check his code.
|
