I fail to see it is cheaper to use arrays of {indices,pointers}. With radix sort the algorithms sequentially goes through the linked list, so the costly linked list operations you are referring to are no issue. With comparison sort algorithms (quicksort,...) you are right (many cmp's, many fwd-backward in de list). With radix sort it is actually smart to use a linked list, so you don't have to prepare for the worst-case scenario when only one bucket contains all the data (note, 2^16 possibilities as 16 bits of the 32 bits are the same) (to take the worst case into account, each buckets needs to be 2^16 bits large, but with 2^16 bits buckets, all the memory is used on a 32-bits machine).
Slashdot Mirror
I fail to see it is cheaper to use arrays of {indices,pointers}. With radix sort the algorithms sequentially goes through the linked list, so the costly linked list operations you are referring to are no issue. With comparison sort algorithms (quicksort, ...) you are right (many cmp's, many fwd-backward in de list). With radix sort it is actually smart to use a linked list, so you don't have to prepare for the worst-case scenario when only one bucket contains all the data (note, 2^16 possibilities as 16 bits of the 32 bits are the same) (to take the worst case into account, each buckets needs to be 2^16 bits large, but with 2^16 bits buckets, all the memory is used on a 32-bits machine).