Code Review Stack Exchange is a question and answer site for peer programmer code reviews. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

I wanted to write a multi-threaded sort, but unfortunately I don't know much about threads, especially in C++11. I managed to make something work, but I would be highly surprised if it was the best way to do it.

template<class T>
void ___sort(T *data, int len, int nbThreads){
        std::sort(data, (&(data[len])), std::less<T>());

        std::future<void> b = std::async(std::launch::async,___sort<T>, data, len/2, nbThreads-2);
        std::future<void> a = std::async(std::launch::async,___sort<T>, &data[len/2], len/2, nbThreads-2);


        std::inplace_merge (data,&data[len/2],&data[len],std::less<T>());

Some of the tests I did sorting integers:

size is the number of ints sorted, and the time is in seconds.

size : 2097152
time with 1 thread : 4.961
time with 2 thread : 3.191
time with 4 thread : 2.377

size : 4194304
time with 1 thread : 10.002
time with 2 thread : 6.214
time with 4 thread : 4.689

size : 8388608
time with 1 thread : 19.975
time with 2 thread : 12.332
time with 4 thread : 9.29

size : 16777216
time with 1 thread : 38.712
time with 2 thread : 25.257
time with 4 thread : 18.706

Also, I tried using std::qsort instead of std::sort, and the results were at least twice as long as that. Any reasons why?

share|improve this question
Don't use '__' in an identifer – Loki Astari Feb 17 '13 at 20:53
I think that one additional optimisation could be to avoid "false sharing" of cache line between threads. The way the buffer is divided this could happen with the current code.. – renoX Feb 26 '13 at 15:09
up vote 2 down vote accepted

Something like this is probably more efficient:

template<class T>
void parallel_sort(T* data, int len, int grainsize)
    // Use grainsize instead of thread count so that we don't e.g.
    // spawn 4 threads just to sort 8 elements.
    if(len < grainsize)
        std::sort(data, data + len, std::less<T>());
        auto future = std::async(parallel_sort<T>, data, len/2, grainsize);

        // No need to spawn another thread just to block the calling 
        // thread which would do nothing.
        parallel_sort(data + len/2, len/2, grainsize);


        std::inplace_merge(data, data + len/2, data + len, std::less<T>());

You could set grain size to something like, std::max(256, len/nb_threads).

share|improve this answer
Yes I don't want 4 threads to sort 8 items. But then again I don't want to spawn more threads than I have parallelism available (not more ((1.0 -> 1.5) * <available cores>)). So I would use a combination of these two techniques. – Loki Astari Feb 17 '13 at 19:40
@LokiAstari: See my suggestion below the code, set grainsize to e.g. std::max(256, len/nb_threads): – ronag Feb 17 '13 at 19:50
parallel_sort(data + len/2, len/2, grainsize); should be: parallel_sort(data + len/2, len - len/2, grainsize); – Fred B May 24 at 10:47

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.