I think the point is if you could build these into hardware. Is the reason this is popular for GPU programming, if I understand correctly. Consider, if you can use this, you can now sort 1024ish elements in 10ish cycles, instead of 10240ish ones. That is rather impressive.
It is algorithms like this that get people very excited about the potential that FPGAs pose, if I understand correctly.
Unless, of course, I completely flubbed my understanding and or math. (Very very possible.)
And then, of course, your point ultimately stands as to why these are not more widely known. For most of us, we have a fixed set of comparators that is very small.
According to Knuth, Batcher's parallel sort was discovered in 1964 and published in 1968. [1] That it's been in Knuth for 35 years of course does not make general unawareness of it unsurprising.
To be a bit snarky, maybe the best piece of hardware to throw first at a sorting problem is a good book on sorting algorithms.
:) Indeed, that is where I just found out about it. Although, do be fair and realize that many of the things in the latest revision of that book are newer than 1978, it was last updated in 1998. (Of course, many are also older...)
I have been going through what is undoubtedly a ridiculous phase of suggesting these books to everyone. I'm doing them in multiple passes where I am mostly skipping exercises for the first pass. Yes, the math is intense. No, they aren't as hard to approach as they have been made out to be.
I'm cheap and that's why I purchased a used older edition. Incidently, though, I recently realized that all the obsolete material on searching tapes as secondary storage is pure Turing machine manipulation.
Anyway, I don't expect to ever master the material, but I learn something every time I open one up.
Still not exactly cheap, but the ebook versions are lower in price. Is what finally got me to read through them. (Well, that mainly because they are easy to take with me, now.) I did save up to buy physical copies, though. Plan to use those to go through the exercises.
It is algorithms like this that get people very excited about the potential that FPGAs pose, if I understand correctly.
Unless, of course, I completely flubbed my understanding and or math. (Very very possible.)
And then, of course, your point ultimately stands as to why these are not more widely known. For most of us, we have a fixed set of comparators that is very small.