In this new version i have changed the partition() function and also i have
used the median of three implementation so that it avoids the worst case
performance. (including the kind .Skybuck Flying was talking about).

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.

It gives:

= 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 quicksort complexity in the best case is:

n * log(n)

You can download parallel quicksort from:

http://pages.videotron.com/aminer/