Groups | Search | Server Info | Keyboard shortcuts | Login | Register [http] [https] [nntp] [nntps]

Groups > comp.programming.threads > #3754 > unrolled thread

My Parallel Sort Library

Back to article view | Back to comp.programming.threads

Contents

  My Parallel Sort Library rami17 <rami17@rami17.net> - 2017-05-06 17:43 -0400

#3754 — My Parallel Sort Library

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.

[toc] | [standalone]

Back to top | Article view | comp.programming.threads

csiph-web