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

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

Parallel Sort

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

Contents

  Parallel Sort aminer <aminer@toto.net> - 2014-06-10 04:33 -0700

#2454 — Parallel Sort

Hello,


As you have noticed i am working on parallelism and synchronization,
the others projects that i have worked on is a Parallel Quicksort and
a better Parallel Sort library, my Parallel Quicksort algorithm is also 
useful cause it avoids worst case performance, for that i have changed 
the partition() function  so that it avoids the worst case performance, 
and also my Parallel Quicksort algorithm uses the median-of-three that 
gives almost 10% better speed.

But if you want something better than my Parallel Quicksort  use my 
Parallel Sort library, my Parallel Sort library implemente 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,
so my Parallel Sort library parallelize both the sort part and the merge 
part and my Parallel Sort library supports Parallel Quicksort, Parallel 
HeapSort and Parallel MergeSort on Multicores systems.

The best case complexity of Parallel Sort library using mergesort  is:

  ((n/p)* log(n/p)) + O(n/p)

p: is the number of cores

the ((n/p)* log(n/p)) is the complexity of the sorting part.

O(n/p) is the best case complexity of the merging part.

so the best case complexity  is:  ((n/p)* log(n/p))



You can download my Parallel Sort library and my
Parallel Quicksort from:

https://sites.google.com/site/aminer68/



Thank you,
Amine Moulay Ramdane.

[toc] | [standalone]

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

csiph-web