- 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

**MergeSort**is easily parallelizable by design: it splitts a source ( input ) data set in half on every recursion call until it reaches a threshold value two or four. Note: A threshold value depends if a data-mining step ( pair-switching ) was performed before processing. >>...Using

**binary search**find index k of the first element in Y greater than X

**binary search**inside of

**MergeSort**will create additional overhead and possibly affect a performance.

- Subscribe to RSS Feed
- Mark Topic as New
- Mark Topic as Read
- Float this Topic for Current User
- Bookmark
- Subscribe
- Printer Friendly Page