Quicksort function using Boost threads

Question

I am having a problem with writing a parallel quicksort using the boost threads library. I have narrowed it down to one snippet of code, this code works but is serial:

void local_quicksort(vector<int>& input)
{
    //Divide vector into equal sized chunks then quicksort the subsections
    for (int i = 0; i < NUM_THREADS; i++)
    {   
        quicksort(input, i * input.size()/NUM_THREADS, (i+1) * input.size()/NUM_THREADS);
    }   
    return;
}

I am trying to use this snippet to parallelize the same function:

void local_quicksort(vector<int>& input)
{
    boost::thread_group bthreads;

    //Divide vector into equal sized chunks for each thread then quicksort the subsections
    for (int i = 0; i < NUM_THREADS; i++)
    {   
        bthreads.create_thread(boost::bind(&quicksort, input, i * input.size()/NUM_THREADS, (i+1) * input.size()/NUM_THREADS));

    }   

    bthreads.join_all();
    return;
}

The part that I can't figure out is that the parallelized version does seem to be calling quicksort (I put a print statement in the quicksort function and it is definitely being called) but no sorting is actually being done (the output is completely unsorted). Can anybody tell me what's happening here?

How do you expect to merge the result of the different quicksort runs? I don't think that is *the* way of implementing a parallel quicksort. — David Rodríguez - dribeas, May 06 '14 at 21:32
I'm going to use a separate function, this quicksort function I'm calling is sorting in place — Dan, May 06 '14 at 21:34
So what is the input, what did you expect the output to look like?... until you do the merge, the vector *won't* be sorted — David Rodríguez - dribeas, May 06 '14 at 21:37
One huge caveat - boost bind take arguments by value, see http://stackoverflow.com/questions/6397092/boostbind-copies-by-reference-or-by-value — Anycorn, May 06 '14 at 21:38
Yeah this is only one section of the code, what I am curious about is why the individual subvectors are not being sorted — Dan, May 06 '14 at 21:41
@Anycorn, that seems to be the issue then, is there a way to pass an argument by reference to boost::bind? — Dan, May 06 '14 at 21:43
@user1023465 yes, use `boost::ref` or pass by pointer. see the question i linked to — Anycorn, May 06 '14 at 21:44
That worked perfect, that's exactly what I was missing thanks so much! — Dan, May 06 '14 at 21:45

Quicksort function using Boost threads

0 Answers0