As I tried to achieve a speed-up in a quicksort algorithm which has to sort 32,000 double variables in an array I encountered some problems.

First, i could'nt see any time between sorting the array filled with random numbers sequentially and parallel. I sorted the array multiple times and tried different numbers for the iterations, but was never able to see any difference between both methods.

Tough I'm quite sure, that I'm using the "sections"-directive correct, as I tried it in another program where i filled tons of double arrays. As I set the number of iterations to a high level, I figured that parallel processing with sections took just half the time of sequential processing.

Here is the quicksort-function in which I can't see any improvement:

- Code: Select all
`void paraQuicksort(double *v, int start, int end)`

{

int i = start, j = end;

double pivot;

// sorting

pivot = v[(start + end) / 2]; // center element

do {

while (v[i] < pivot)

i++;

while (pivot < v[j])

j--;

if (i <= j)

{ // only if both indices do not touch

swap(v, i, j);

i++;

j--;

}

} while (i <= j);

#pragma omp parallel sections

#pragma omp section

{

if (start < j)

{

paraQuicksort(v, start, j); // divides left segment

}

}

#pragma omp section

{

if (i < end)

{

paraQuicksort(v, i, end); // divides right segment

}

}

}

I'm using the gcc compiler v. 4.6.3 under Ubuntu 12.xx with an Intel i-7 processor. As I compile it with the -fopenmp and a gcc version above 4.4 I suppose I also run openMP 3.x.

I know that the quicksort algorithm performs right, but almost every cases I tried the parallel algorithm performed worse than or at least equal as the sequentiell algorithm.

My question is, if it is normal, that i don't see any improvement of the time used to perform this task (maybe because of the overhead which is created by using additional threads for a relatively simple task like this), altough quicksort seems to be a frequently used example in sectioning, or if I just missed a point in setting up the sectioning for recursive parts.

I would be glad if someone could help me with my little problem and apologize for missing information you may need.

With best regards,

Nyran