Parallel quick sort not running faster than sequential quick sort

Question

My quicksort works fine it outputs correctly but the parallel version does not execute faster than the non parallel version. What else can I do to it to make it run faster?

void quickSort(int arr[], int low, int high)
{
    int pi;
    if (low < high)
    {
        //pi is partitioning index, arr[p] is now at right place 
        pi = partition(arr, low, high);
        // Separately sort elements before partition and after partition
        quickSort(arr, low, pi - 1);
        quickSort(arr, pi + 1, high);
    }
}

void quickSort_parallel_omp(int arr[], int low, int high)
{
    int pi;
    if (low < high)
    { 
        pi = partition(arr, low, high);
        omp_set_nested(1);
        #pragma omp parallel sections num_threads(Nthreads)
        {           //Nthreads is declared in the main as int Nthreads = 4
            #pragma omp section
            quickSort_parallel_omp(arr, low, pi - 1);
            #pragma omp section
            quickSort_parallel_omp(arr, pi + 1, high);
        }
    }
}

[Many things](https://stackoverflow.com/questions/3969813/which-parallel-sorting-algorithm-has-the-best-average-case-performance). — nwp, Nov 27 '17 at 16:59
How large is the array? Starting a new thread also takes some time, so it has to do enough work to earn that time back. And then some. — Bo Persson, Nov 27 '17 at 17:01
For 20 elements, the overhead of firing up and coordinating multiple threads will swamp any benefit. Parallel processing is most beneficial for large problems. — Pete Becker, Nov 27 '17 at 20:44

score 1 · Answer 1 · answered Nov 27 '17 at 17:05

It might be that the overhead for distributing the data into multiple parallel processing units and combining the result back again exceeds the performance gain due to parallelising the code. I'd suggest you to increase your input size to see a considerable performance gain.

score 0 · Answer 2 · answered Nov 27 '17 at 17:47

In your case the time to create thread, allocating memory and time slice by O/S to each thread is taking more time than time taken to short the data.

Performance of parallel processing can be seen only when it process large volume of data. Besides lots of other factors also need to be considered in multiprocessing or parallel processing, like system memory number of processors etc. You can get lots of online document on this topic.

Parallel quick sort not running faster than sequential quick sort

2 Answers2