parallel_merge_sort

#include <thread>
#include <random>
#include <vector>
#include <iostream>
#include <numeric>
#include <algorithm>
/*
size_t binarySearch(int x, std::vector<int> arr, size_t left, size_t right) {
    if (right <= left)
        return left;
    if (x < arr[left])
        return left;
    while (right - left > 1) {
        size_t mid = (right + left) / 2;
        if (arr[mid] < x)
            left = mid;
        else
            right = mid;
    }
    return right;

}*/

void merge1(std::vector<int>& arr, size_t left1, size_t right1, size_t left2, size_t right2, std::vector<int>& res, size_t left3) {
    size_t n1 = right1 - left1, n2 = right2 - left2;
    if (n1 < n2) {
        std::swap(left1, left2);
        std::swap(right1, right2);
        std::swap(n1, n2);
    }
    if (n1 == 0) {
        return;
    }
    size_t mid1 = (right1 + left1) / 2;
    size_t mid2 = std::lower_bound(arr.begin() + left2, arr.begin() + right2, arr[mid1]) - arr.begin(); //binarySearch(arr[mid1], arr, left2, right2);
    size_t mid3 = left3 + (mid1 - left1) + (mid2 - left2);
    res[mid3] = arr[mid1];
    std::thread first(merge1, std::ref(arr), left1, mid1, left2, mid2, std::ref(res), left3);
    std::thread second(merge1, std::ref(arr), mid1 + 1, right1, mid2, right2, std::ref(res), mid3 + 1);
    first.join();
    second.join();
}

void merge(std::vector<int>& arr, size_t left, size_t mid, size_t right) {
    std::vector<int> res(right - left);
    merge1(arr, left, mid, mid, right, res, 0);
    for (size_t i = left; i < right; i++) {
        arr[i] = res[i - left];
    }
}

void mergeSort(std::vector<int>& arr, size_t left, size_t right)
{
    if (right - left <= 1)
        return;

    size_t mid = (right + left) / 2;
    std::thread first(mergeSort, std::ref(arr), left, mid);
    std::thread second(mergeSort, std::ref(arr), mid, right);
    first.join();
    second.join();
    merge(arr, left, mid, right);
}

int main() {
    std::vector<int> arr = { 5,4,3,2,1 };
    mergeSort(arr, 0, arr.size());
    return 0;
}