MergeSortThreaded.cpp

#include <iostream>
#include <vector>
#include <thread>
#include <future>

template<typename T>
std::vector<T> merge (std::vector<T>const& a, std::vector<T> const& b) {
    std::vector<T> result;

    auto itA = a.begin(), itAEnd = a.end();
    auto itB = b.begin(), itBEnd = b.end();

    // put the elements on result vector
    while (itA != itAEnd && itB != itBEnd) {
        if (*itA < *itB)
            result.push_back(*itA++);
        else
            result.push_back(*itB++);
    }

    // ensure that all elements were pushed
    // Note: only one of those will do any operations
    while (itA != itAEnd)
        result.push_back(*itA++);
    while (itB != itBEnd)
        result.push_back(*itB++);

    return result;
};

template<typename T>
std::vector<T> MergeSort (std::vector<T>const& data) {
    // check for end condition
    if (data.size() == 1)
        return data;

    // split the data
    unsigned splitN = data.size() / 2;
    auto split = data.begin() + splitN;

    std::future<std::vector<T>> rA = std::async(std::launch::async, MergeSort<T>, std::vector<T>(data.begin(), split));
    std::future<std::vector<T>> rB = std::async(std::launch::async, MergeSort<T>, std::vector<T>(split, data.end()));

    return merge(rA.get(), rB.get());
}

int main () {
    std::vector<int> V;
    V.push_back(4);
    V.push_back(1);
    V.push_back(6);
    V.push_back(18);
    V.push_back(9);
    V.push_back(7);
    V.push_back(0);

    auto R = MergeSort(V);
    for (auto i : R) {
        std::cout << i << " ";
    }
    std::cout << '\n';
}