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

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

About the algorithms of my ParallelSort library

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

Contents

  About the algorithms of my ParallelSort library Horizon68 <horizon@horizon.com> - 2019-03-25 12:31 -0700

#4965 — About the algorithms of my ParallelSort library

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.

[toc] | [standalone]

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

csiph-web