About parallel merging paper...
I have just read the following paper on Parallel Merging:
And i have implemented this algorithm just to see what is the performance.
And i have noticed that the serial algorithm is 8 times slower
than the merge function that you find in the serial mergesort algorithm.
So 8 times slower, it's too slow.
It's better to use the following algorithm;
The idea is simple:
Let's assume we want to merge sorted arrays X and Y. Select X[m] median
element in X. Elements in X[ .. m-1] are less than or equal to X[m].
Using binary search find index k of the first element in Y greater than
Thus Y[ .. k-1] are less than or equal to X[m] as well. Elements in X[m+1
are greater than or equal to X[m] and Y[k .. ] are greater. So merge(X, Y)
can be defined as concat(merge(X[ .. m-1], Y[ .. k-1]), X[m], merge(X[m+1
... ], Y[k .. ]))
now we can recursively in parallel do merge(X[ .. m-1], Y[ .. k-1]) and
merge(X[m+1 .. ], Y[k .. ]) and then concat results.
And then you can continue to apply this method recursivily.
Amine Moulay Ramdane.
|All times are GMT. The time now is 07:16 PM.|
Powered by vBulletin®. Copyright ©2000 - 2014, vBulletin Solutions, Inc.
SEO by vBSEO ©2010, Crawlability, Inc.