3 ms·
I always ask in these threads, what sort of data do you have that cannot be divided into several integers, such that sorting by those integers according to some
by anonymoushn 2y ago
I always ask in these threads, what sort of data do you have that cannot be divided into several integers, such that sorting by those integers according to some priority implements your comparator correctly, and also your comparator is not so expensive as to be impractical? on one occasion someone replied "sorting unicode strings in collation order" but it doesn't seem like recomputing the collation inside of each comparison is practical, and the cache behavior of comparison sorts if you precompute all of them (spending several times the memory occupied by the input) will be quite bad.
structs containing strings and doubles for example are well suited to radix sort.
- yorwba 2y agoA sequence of integers such that sorting by those integers implements the comparator correctly is precisely what the Unicode Collation Algorithm produces as its sort key. https://www.unicode.org/reports/tr10/#Scope https://www.unicode.org/reports/tr10/#Scope
- anonymoushn 2y agoYes.
- shiandow 2y agoBest I've been able to come up with is fractions. Though true fractions are rare (and can be converted to a sequence of integers that can be sorted lexicographically, see continued fractions). Technically floats qualify, but not in an interesting way since you basically just need to take care of the sign bit and a few special cases. Really most things can be sorted with radix sort, though I wouldn't want to be the one having to implement it for unicode strings (sorting text in general is one of those problems you'd preferably let other people solve for you).
- anonymoushn 2y agofractions is a great answer!