Making a faster parallel quicksort I'm trying to take my existing parallel Quicksort and make it execute faster. Below is what I have but half the time the optimized version doesn't give me a faster time. 

I use them to compare big arrays whose sizes are 10,000 or more. Any advice on what I should change? Nthreads is declared in the main function and set to 4.

void quickSort_parallel_omp(int arr[], int low, int high)
{
    int pi; 
    if (low &lt; high)
    {
        pi = partition(arr, low, high);
        omp_set_nested(1);                               
        #pragma omp parallel sections
        {
            #pragma omp section
            quickSort_parallel_omp(arr, low, pi - 1);
            #pragma omp section
            quickSort_parallel_omp(arr, pi + 1, high);
        }
    }
}


void quickSort_Optparallel_omp(int arr[], int low, int high)   //optimized version
{
    int pi; 
    if (low &lt; high)
    {
        pi = partition(arr, low, high);
        omp_set_nested(1);                               
        #pragma omp parallel sections num_threads(Nthreads) 
        {
            #pragma omp section
            quickSort_Optparallel_omp(arr, low, pi - 1);
            #pragma omp section
            quickSort_Optparallel_omp(arr, pi + 1, high);
        }
    }
}
Nested parallelism is expensive. It was designed for around 1 nesting level when the first level is not parallel enough, and loop slicing. This kind of recursive problems are much better handled by tasks.

void quickSort_tasks(int arr[], int low, int high)
{
    int pi; 
    if (low &lt; high)
    {
        pi = partition(arr, low, high);
        #pragma omp task
        quickSort_Optparallel_omp(arr, low, pi - 1);
        #pragma omp task
        quickSort_Optparallel_omp(arr, pi + 1, high);
    }
}

void quickSort_omp(int arr[], int low, int high) {
   #pragma omp parallel
   #pragma omp single
   quickSort_tasks(arr,low,high);
   // implicit synchronization at the end of parallel section
   // otherwise use 
   // #pragma omp taskwait
}


Other sorting algorithms may offer higher performance or more efficient parallelization, although being algorithmically more complex. I'm thinking about radix, pigeonhole and merge sorting.

Parallel radix sort explanation: http://projects.csail.mit.edu/wiki/pub/SuperTech/ParallelRadixSort/Fast_Parallel_Radix_Sort_Algorithm.pdf