Parallel Quicksort has been updated to version 1.06, i have stress tested it
and it didn't show any problem.
Parallel Quicksort is an implementation of the median-of-three that gives
almost 10% better speed.
Parallel Quicksort gave me almost 3x scaling when sorting strings and
integers on a quad cores,
and now in version 1.06 you can use it also in an hybrid manner with
mergsort, just by passing
ctmergesort to the constructor it will give 10% better speed.
And as you know , Quicksort is a divide and conquer algorithm that have the
following best case performance:
T(n) = T(n/2) + T(n/2) + O(n)
= 2T(n/2) + (n)
cause it take O(n) for the partition part.
= 2 (2T(n/4) +n/2) + n
=4 (2T(n/8) +n/4) + 2*n
=2k T(n/2^k) + k*n
n/2k = 1
n = 2k
log n = k
so the reccurence equation gives:
= nT(1) +n*log(n)
= n+ (n * log(n))
So the quicksort complexity in the best case is:
n * log(n)
But the complexity of the quicksort in the worst case is:
T(n)= n + T(n-1)
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 quicksort from:
Amine Moulay Ramdane.