- Mark as New
- Bookmark
- Subscribe
- Mute
- Subscribe to RSS Feed
- Permalink
- Report Inappropriate Content
Hello,
I have just read the following paper on Parallel
Merging:
http://www.economyinformatics.ase.ro/content/EN4/alecu.pdf
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;
http://www.drdobbs.com/parallel/parallel-merge/229204454?queryText=parallel%2Bsort
The
idea is simple:
Let's assume we want to merge sorted arrays X and Y.
Select X
element in X. Elements in X[ .. m-1] are less than or
equal to X
Using binary search find index k of the first element in Y
greater than
X
Thus Y[ .. k-1] are less than or equal to X
are greater than or equal to X
can be defined as concat(merge(X[ .. m-1], Y[ ..
k-1]), X
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.
Thank you,
Amine Moulay Ramdane.
Link Copied
- Mark as New
- Bookmark
- Subscribe
- Mute
- Subscribe to RSS Feed
- Permalink
- Report Inappropriate Content
- Mark as New
- Bookmark
- Subscribe
- Mute
- Subscribe to RSS Feed
- Permalink
- Report Inappropriate Content
- Subscribe to RSS Feed
- Mark Topic as New
- Mark Topic as Read
- Float this Topic for Current User
- Bookmark
- Subscribe
- Printer Friendly Page