3 ms·
Yes, sorting typically (and this one specifically) has long dependency chains. The natural reflex is to split the chains across multiple workers... and that's
by klyrs 7y ago
Yes, sorting typically (and this one specifically) has long dependency chains. The natural reflex is to split the chains across multiple workers... and that's how you get merge-sort. But even the last pass has a linear dependence chain. Not long ago, somebody posted a clever algorithm based on 4-way swaps, which is a clever way of addressing the issue.
Edit: I can't seem to locate that 4-way swapping algorithm, I swear it was posted to HN in the last year... somebody halp!