My Parallel Sort Library

[rami17]

Hello......

I have implemented a Parallel hybrid divide-and-conquer merge algorithm
that performs 0.9-5.8 times better than sequential merge, on a quad-core
processor, with larger arrays outperforming by over 5 times. Parallel
processing combined with a hybrid algorithm approach provides a powerful
high performance result.

The idea:

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 now ParallelSort library gives better performance and scalability.

You can download my powerful Parallel Sort Library from:

https://sites.google.com/site/aminer68/parallel-sort-library

Thank you,
Amine Moulay Ramdane.