News for hackers. Stuff that matters.
Re:Parallel In-Place Merge Sort by brudgers on Wednesday October 01, 2014 @08:12AM (#8393887)
While the approximately 10x increase of the parallel in-place merge sort over the non-parallel version shown on the benchmarks may be meaningful, it also shows that parallelism reduces constant factors, not exponents.
Re:Parallel In-Place Merge Sort by taeric on Wednesday October 01, 2014 @09:49AM (#8394254)
If you have a look at sorting networks, they actually do reduce an exponent. Goes from nlg(n) to just lg(n). See [1], for example.

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...

Re:Parallel In-Place Merge Sort by brudgers on Wednesday October 01, 2014 @10:03AM (#8394346)
[Assumption: n is large enough to make the problem interesting]

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.

Re:Parallel In-Place Merge Sort by taeric on Wednesday October 01, 2014 @10:17AM (#8394446)
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.

Re:Parallel In-Place Merge Sort by brudgers on Wednesday October 01, 2014 @10:43AM (#8394731)
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.

[1] TAoCP: Volume 3 [1978], page 111

Re:Parallel In-Place Merge Sort by taeric on Wednesday October 01, 2014 @11:06AM (#8394975)
:) 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.

Re:Parallel In-Place Merge Sort by brudgers on Wednesday October 01, 2014 @12:27PM (#8395674)
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.

Re:Parallel In-Place Merge Sort by taeric on Wednesday October 01, 2014 @02:21PM (#8396588)
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.
Re:Parallel In-Place Merge Sort by readerrrr on Wednesday October 01, 2014 @09:11AM (#8394079)
It is impossible to get anything better than a constant improvement, if you divide you work by a constant factor.
Re:Parallel In-Place Merge Sort by brudgers on Wednesday October 01, 2014 @09:50AM (#8394256)
Not discussing that is a weakness of the article. The algorithm addresses performance issues caused by the IO bottleneck, not an algorithmic deficiency with common merge-sort implementations.

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.

Re:Parallel In-Place Merge Sort by sp332 on Wednesday October 01, 2014 @10:10AM (#8394403)
That's just what brudgers said. But don't worry, CPU and GPU manufacturers are increasing the number of cores exponentially :p