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

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

X[m].

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.

Thank you,

Amine Moulay Ramdane.