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

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

Parallel Sort Library version 3.1

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

Contents

  Parallel Sort Library version 3.1 aminer <aminer@toto.net> - 2014-05-08 13:13 -0700

#2320 — Parallel Sort Library version 3.1

Hello,

I have updated my Parallel Sort Library to version 3.1,
i have just corrected a bug and it is stable now,
and it gives better scalability than my Parallel Quicksort.

The best case complexity of my 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))

The worst case complexity of parallel sort library using mergesort is:

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

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

O(n) is the worst  case complexity of the merging part.

so the worst case complexity of parallelsort using mergesort is 
approximatly: O(n)



You can download my Parallel Sort library 3.1 from:

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




Thank you,
Amine Moulay Ramdane.

[toc] | [standalone]

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

csiph-web