parallel quicksort in C++11

quick_sort_mt.cpp

/**
 * g++ -std=c++14 quick_sort_mt.cpp -pthread && ./a.out 10000 1 1
 *
 *
 * This works:
 * ./a.out 10000 1 1
 *
 * This fails (unpredictably!):
 * ./a.out 100000 1 1
 **/
#include <algorithm>
#include <cassert>
#include <functional>
#include <future>
#include <iterator>

namespace user { namespace algorithm {

bool multithreaded = false;
size_t partition_size = 1000000;

template <class ForwardIterator,
    typename Compare=std::less<
        typename std::iterator_traits<ForwardIterator>::value_type
    >
>
void quicksort(ForwardIterator first, ForwardIterator last, Compare comp = Compare())
{
    using value_type = typename std::iterator_traits<ForwardIterator>::value_type;
    using difference_type = typename std::iterator_traits<ForwardIterator>::difference_type;
    difference_type dist = std::distance(first,last);
    assert(dist >= 0);
    if (dist < 2)
    {
        return;
    }
    else if (dist < partition_size)
    {
        std::sort(first,last);
    }
    else
    {
        auto pivot = *std::next(first, dist/2);
        auto     ucomp = [pivot,&comp](const value_type& em){ return  comp(em,pivot); };
        auto not_ucomp = [pivot,&comp](const value_type& em){ return !comp(pivot,em); };

        auto middle1 = std::partition(first, last, ucomp);
        auto middle2 = std::partition(middle1, last, not_ucomp);

        auto policy = multithreaded ? std::launch::async : std::launch::deferred;
        auto f1 = std::async(policy, [first  ,middle1,&comp]{quicksort(first  ,middle1,comp);});
        auto f2 = std::async(policy, [middle2,last   ,&comp]{quicksort(middle2,last   ,comp);});
        f1.wait();
        f2.wait();
    }
}

template <typename Container>
void sort(Container& arr)
{
    user::algorithm::quicksort(arr.begin(),arr.end());
}

}} // namespace user::algorithm

#include <iostream>
#include <random>
#include <vector>

using std::cout;
using std::endl;

int main(int argc, char** argv)
{
    int seed = 1;
    size_t array_size = atoi(argv[1]);
    user::algorithm::partition_size = atoi(argv[2]);
    user::algorithm::multithreaded = bool(atoi(argv[3]));

    std::random_device rd;
    std::mt19937 gen(seed);
    std::uniform_real_distribution<> dis(0, 1000);

    std::vector<double> arr(array_size);

    cout << "generating random array..."; cout.flush();
    for (auto& i : arr)
    {
        i = dis(gen);
    }
    cout << "done.\n";

    cout << "sorting..."; cout.flush();
    user::algorithm::sort(arr);
    cout << "done.\n";

    cout << "verifying..."; cout.flush();
    auto i = arr.begin();
    auto j = i+1;
    while (j != arr.end())
    {
        if (*i > *j)
        {
            cout << "array not sorted.\n";
            cout << *i << " > " << *j << endl;
            cout << "at indexes: " << std::distance(arr.begin(),i)
                 << " and " << std::distance(arr.begin(),j) << endl;
            cout << "context:\n";
            auto a = std::distance(arr.begin(),i);
            auto b = std::distance(arr.begin(),j);
            auto space = false;
            for (auto x : {a-3,a-2,a-1,a,a+1,a+2,a+3}) {
                cout << (space ? ", " : (space=true,"")) << *(arr.begin()+x);
            }
            cout << endl;
            return -1;
        }
        ++i;
        ++j;
    }
    cout << "array sorted!\n";
}