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

Groups > comp.programming.threads > #4987

My new and more efficient Parallel Sort Library is here..

Show all headers | View raw

Hello,

Read this:


My new and more efficient Parallel Sort Library is here..

Here is what have changed:

My algorithm of finding the median of Parallel merge of my Parallel Sort 
Library that you will find here in my website:

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

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). But this new 
algorithm of finding the median of parallel merge of my Parallel Sort 
Library is O(log(|A|+|B|)), which is slightly worse. With further 
optimizations the order was reduced to O(log(2*min(|A|,|B|))), which is 
better, but is 2X more work, since both arrays may have to be searched. 
All algorithms are logarithmic. Two binary searches were 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 
parallel merge sort.


You can download it from:

https://sites.google.com/site/scalable68/parallel-sort-library-that-is-more-efficient



Thank you,
Amine Moulay Ramdane.

Back to comp.programming.threads | Previous | Next | Find similar | Unroll thread

Thread

My new and more efficient Parallel Sort Library is here.. Horizon68 <horizon@horizon.com> - 2019-04-01 10:55 -0700

csiph-web