If a sorting network (such as Batcher's} requires O(n (log n)^2)[Space] doesn't this sort of defeat the purpose of trying to sort in-place?...since a traditional array copying merge-sort has 0(n)[Space] requirements.
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.
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.
[1] TAoCP: Volume 3 [1978], page 111
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.
Anyway, I don't expect to ever master the material, but I learn something every time I open one up.
Saying that, I feel like I'm trying to mislead, though. This requires nlg(n) comparators, so you still have to pay for it somehow. And I doubt we are going to see that many comparators on any piece of kit any time soon. For large n, anyway. (Though, seeing this can be done with a gpu, it does seem that you can hit rather large arrays already.)
[1] http://en.wikipedia.org/wiki/Batcher_odd%E2%80%93even_merges...