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...
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.
The merits and deficits of trading-off O(n)[Memory] growth for 0(log n)^2[Time] growth are worthy of discussion if it is anticipated that people will implement the algorithm in production code. There's a case for looking at it, certainly, on constrained systems, but such systems may not have processors with the execution pipeline sophistication of an Intel i7 quad-core.
Which of course is just a round about way of saying, the article doesn't indicate domains in which the algorithm may be relevant and not relevant.