multithreaded mergesort

Question

I wrote mergesort algorithm, and it works fine. Then i have commented recursive calls of function, and tried to use some boost::threads like this:

#include <iostream>
#include <vector>
#include <boost/thread.hpp>

void merge_sort(std::vector <int> & tab, size_t beg, size_t end)
{
    if(beg < end)
    {
        size_t pivot = (beg + end) >> 1;

        boost::thread left(merge_sort, tab, beg, pivot);
        //merge_sort(tab, beg, pivot);
        boost::thread right(merge_sort, tab, pivot + 1, end);
        //merge_sort(tab, pivot + 1, end);
        left.join();
        right.join();

        std::vector <int> buf (tab);
        size_t i = beg, j = pivot + 1, q = beg;
        while (i <= pivot && j <= end)
        {
            if (buf[i] < buf[j])
                tab[q++] = buf[i++];
            else
                tab[q++] = buf[j++];
        }
        while (i <= pivot)
            tab[q++] = buf[i++];
    }
}

int main()
{

    const int myints[] = {30,29,28,27,26,25,1,2,3,4,5,6,7,24,23,22,21,20,19,18,8,9,10,11,17,16,15,13,45,12};
    std::vector <int> kontener (myints, myints + sizeof(myints) / sizeof(int) );

    merge_sort(kontener, 0, kontener.size() - 1);

    for(std::vector <int>::iterator it = kontener.begin(); it != kontener.end(); it++)
        std::cout << *it << " ";
    std::cout << std::endl;

    std::cin.sync();
    std::cin.get();
    return(0);
}

But i've got wrong output with this threads. :P I would be therefore gratefull if somebody could tell me what is wrong with this code.

Answer 1

You are not actually passing the vector to the sub-threads as a reference, even if it may seem so. You need to use boost::ref or std::ref. Also note that the buffer only has to be as big as the section you are currently working on, there is no point in copying the entire vector all the time:

    boost::thread left(merge_sort, boost::ref(tab), beg, pivot);
    boost::thread right(merge_sort, boost::ref(tab), pivot + 1, end);
    left.join();
    right.join();

    std::vector <int> buf (tab.begin()+beg, tab.begin()+end+1);
    size_t i = beg, j = pivot + 1, q = beg;
    while (i <= pivot && j <= end)
    {
        if (buf[i-beg] < buf[j-beg])
            tab[q++] = buf[i++ - beg];
        else
            tab[q++] = buf[j++ - beg];
    }
    while (i <= pivot)
        tab[q++] = buf[i++ - beg];

(Also note that this code might well be a bit cleaner if you used iterators and standard algorithms, but for the sake of simplicity, I've kept your structure.)