Path: csiph.com!eternal-september.org!feeder.eternal-september.org!news.eternal-september.org!.POSTED!not-for-mail
From: rami17 <rami17@rami17.net>
Newsgroups: comp.programming.threads
Subject: My Parallel Sort Library
Date: Sat, 6 May 2017 17:43:18 -0400
Organization: A noiseless patient Spider
Lines: 28
Message-ID: <oelfri$99a$2@dont-email.me>
Mime-Version: 1.0
Content-Type: text/plain; charset=utf-8; format=flowed
Content-Transfer-Encoding: 7bit
Injection-Date: Sat, 6 May 2017 21:40:02 -0000 (UTC)
Injection-Info: mx02.eternal-september.org; posting-host="ec33f296fa4b991c65b44a52e3723406"; logging-data="9514"; mail-complaints-to="abuse@eternal-september.org";	posting-account="U2FsdGVkX19iU/XRl/1csVbQGRWA10ti"
User-Agent: Mozilla/5.0 (Windows NT 10.0; WOW64; rv:45.0) Gecko/20100101 Thunderbird/45.8.0
X-Mozilla-News-Host: news://news.eternal-september.org:119
Cancel-Lock: sha1:+1u5hoMZbSVoJedMnxwKWSyQBGg=
Xref: csiph.com comp.programming.threads:3754

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.