Read again, i correct a little mistake..

[Horizon68]

Hello,


Read again, i correct a little mistake..

My Parallel Sort Library was updated to version 3.6

I have enhanced it more, and now it scales more and it is
faster.

Description:

My Parallel Sort Library that supports Parallel Quicksort, Parallel
HeapSort and Parallel MergeSort on Multicores systems.

Parallel Sort Library uses my Thread Pool Engine and sort many array
parts - of your array - in parallel using Quicksort or HeapSort or
MergeSort and after that it finally merge them - with the merge()
procedure -

In the previous parallelsort version i have parallelized only the sort
part, but in this new parallelsort version i have parallelized also the
merge procedure part and it gives better performance.

My new parallel sort algorithm has become more cache-aware, and i have
done some benchmarks with my new parallel algorithm and it has given up
to 5X scalability on a Quadcore when sorting strings, other than that i
have cleaned more the code and i think my parallel Sort library has
become a more professional and industrial parallel Sort library , you
can be confident cause i have tested it thoroughly and no bugs have
showed , so i hope you will be happy with my new Parallel Sort library.

My algorithm of finding the median in Parallel merge is
O(log(min(|A|,|B|))), where |A| is the size of A, since the binary
search is performed within the smaller array and is O(lgN).

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.


You can download it from:

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



Thank you,
Amine Moulay Ramdane.