Parallel Quicksort

As my parallel mergesort implementation was very memory dependent, I wanted to write a parallel quicksort one. Here it comes:

template
In partition(In b, In e) {
    // create uniform distribuiton for random engine
    std::uniform_int_distribution rand_distribution(0, std::distance(b, e - 1));

    // call static random engine to get index of random pivot
    tbb::spin_mutex::scoped_lock lock;
    lock.acquire(mutex);
    auto rand_pivot_index = rand_distribution(rand_engine);
    lock.release();

    // put pivot to last place in range
    std::swap(*(b + rand_pivot_index), *(e - 1));

    // save pivot value
    auto pivot = *(e - 1);
    auto pivotiterator = b;

    // sort the range
    for(auto it = b; it != e - 1; ++it) {
        if(*it 
void quick_sort_parallel(In b, In e) {
    if (b != e) {
        In m = partition(b, e);

        // switch to different sort on worst case or smaller ranges
        if(std::distance(b, m) > 500) {
            tbb::parallel_invoke([&] { quick_sort_parallel(b, m); }, 
                                 [&] { quick_sort_parallel(m + 1, e); });
        }
        else 
            merge_sort_parallel(b, e); //defined somewhere else, pretty standard
    }
}

Code

I would suggest using RAII for your lock.

Instead of:

std::uniform_int_distribution rand_distribution(0, std::distance(b, e - 1));

// call static random engine to get index of random pivot
tbb::spin_mutex::scoped_lock lock;
lock.acquire(mutex);
auto rand_pivot_index = rand_distribution(rand_engine);
lock.release();

// put pivot to last place in range
std::swap(*(b + rand_pivot_index), *(e - 1));

Use:

std::uniform_int_distribution rand_distribution(0, std::distance(b, e - 1));

// call static random engine to get index of random pivot
int rand_pivot_index;
{
    tbb::spin_mutex::scoped_lock lock(mutex);
    rand_pivot_index = rand_distribution(rand_engine);
}

// put pivot to last place in range
std::swap(*(b + rand_pivot_index), *(e - 1));

This ensures that if rand_distribution throws, the lock is released correctly.

Algorithm

Choice of pivot is important in any quick-sort algorithm, and even more so in the parallel case, when you want to garuntee a good distribution of load over cores by avoiding unbalanced recursion.

A good basic strategy is to choose the median of k random elements as your pivot.

Taking this further, using a median of medians algorithm can guarantee your quicksort a O(n log n) running time.

The correct approach and value of k will largely depend on the inputs your function will expect to take (e.g. adapt k based on size on input).

StackExchange Code Review Q#7870, answer score: 6