Hello all,
I have done some tests with my ParallelSort library and
i have noticed that it can give up to 3.8x scalability with
strings, and it give 3x scalability with integers..
The complexity of ParallelSort using mergesort for exemple, is:
((n/p)* log(n/p)) + O(n/p)
And as you know:
If f1 is O(g1) and f2 is O(g2),
then f1 + f2 is O(max (f1, f2)), where
max (f1, f2) (x) = max (f1 (x), f2 (x)); for every x
So the complexity of my Parallel Sort library using mergesort
is:
(n/p)* log(n/p)) // p is the number of cores.
Also i have implemented Parallel MergeSort and Parallel Quicksort,
but MergeSort is faster and the reccurence equation of the complexity of mergesort is:
T(n) = 2 * T(n/2) + n
cause it take O(n) for the merging part.
It gives:
T(n) = 2 * T(n/2) + n
= 2 (2T(n/4) +n/2) + n
=4T(n/4)+n+n
=4T(n/4)+2*n
=4 (2T(n/8) +n/4) + 2*n
=8T(n/8)+n+2n
=8T(n/8)+3*n
=2k T(n/2^k) + k*n
We want:
n/2k = 1
n = 2k
log n = k
so the reccurence equation gives:
= nT(1) +n*log(n)
= n+ (n * log(n))
So the mergesort complexity in the best case and in the worst case is:
n * log(n)
But the complexity of the quicksort in the worst case is:
T(n)= n + T(n-1)
it gives:
T(n) = n + (n-1) + T(n-2)
T(n) = n + (n-1) + (n-2)+ T(n-3)
T(n) = 1 + 2+ 3+.+N
T(n) = O(n^2) // n power of 2
You can download Parallel Sort library from:
http://pages.videotron.com/aminer/Thank you,
Amine Moulay Ramdane.