5 ms·
As the other posts have said, this isn't the right algorithm. Onesweep and its kin are cool but intimidating. The magic is easier to understand if one looks int
by spenczar5 2y ago
As the other posts have said, this isn't the right algorithm. Onesweep and its kin are cool but intimidating. The magic is easier to understand if one looks into the core algorithm: radix sort.
A very readable explanation is here: https://gpuopen.com/download/publications/Introduction_to_GPU_Radix_Sort.pdf https://gpuopen.com/download/publications/Introduction_to_GP...
It turns out that radix sort can be implemented in a way that is very straightforward to parallelize. It's a beautiful and elegant approach and worth knowing about!
- torginus 2y agoYeah, but radix sort requires you to have an ordered integer key, not just two objects being comparable, like with most general sorting techniques.
- anonymoushn 2y agoI 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!