About the algorithms of my ParallelSort library

[Horizon68]

Hello..


About the algorithms of my ParallelSort library:


My algorithm of my ParallelSort libray 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.


I will enhance the above algorithm of finding the median with a new
efficient algorithm that is O(log(2*min(|A|,|B|))) that is 2X more work,
since both arrays may have to be searched. Two binary searches are
necessary to find an even split that produced two equal or nearly equal
halves. Luckily, this part of the merge algorithm is not performance
critical. So, more effort can be spent looking for a better split. This
new algorithm in the parallel merge balances the recursive binary tree
of the divide-and-conquer and improve the worst-case performance of my
ParallelSort library.


So stay tuned my ParallelSort library with this new algorithm above is
coming soon !


Thank you,
Amine Moulay Ramdane.