#include <thread>
#include <mutex>
#include <iostream>

using namespace std;

void merge_sort_recursive_par(int arr[], int reg[], const int start, const int end) {
    thread threads[thread::hardware_concurrency()];
    if (start >= end)
        return;
    int len = end - start, mid = (len >> 1) + start;
    int start1 = start, end1 = mid;
    int start2 = mid + 1, end2 = end;
    int iter = thread::hardware_concurrency();
    int iter1 = thread::hardware_concurrency();

    mutex mu;
    mu.lock();
	for (int i = 0; i < thread::hardware_concurrency(); i++)
    {
		if (!threads[i].joinable())
        {
			threads[i] = thread(merge_sort_recursive_par, arr, reg, start1, end1);
			iter = i;
			break;
		};
	}

	for (int j = 0; j < thread::hardware_concurrency(); j++)
    {
		if (!threads[j].joinable())
        {
			threads[j] = thread(merge_sort_recursive_par, arr, reg, start2, end2);
			iter1 = j;
		    break;
		};

	}
    mu.unlock();

    if (iter < thread::hardware_concurrency())
    {
      threads[iter].join();

    };
    if (iter1 < thread::hardware_concurrency())
    {
      threads[iter1].join();
    };

    if (iter == thread::hardware_concurrency())
    {
		merge_sort_recursive_par (arr, reg, start1, end1);
	}

	if (iter1 == thread::hardware_concurrency())
    {
		merge_sort_recursive_par (arr, reg, start2, end2);
	}
    // merge_sort_recursive (arr, reg, start1, end1);
    // merge_sort_recursive (arr, reg, start2, end2);

    int k = start;
    while (start1 <= end1 && start2 <= end2)
        reg[k++] = arr[start1] < arr[start2] ? arr[start1++] : arr[start2++];
    while (start1 <= end1)
        reg[k++] = arr[start1++];
    while (start2 <= end2)
        reg[k++] = arr[start2++];
    for (k = start; k <= end; k++)
        arr[k] = reg[k];
}

void merge_sort_par(int arr[], const int len) {
    int reg[len];
    merge_sort_recursive_par(arr, reg, 0, len - 1);
}

void merge_sort_recursive_pos(int arr[], int reg[], const int start, const int end) {
    if (start >= end)
        return;
    int len = end - start, mid = (len >> 1) + start;
    int start1 = start, end1 = mid;
    int start2 = mid + 1, end2 = end;

    merge_sort_recursive_pos (arr, reg, start1, end1);
    merge_sort_recursive_pos (arr, reg, start2, end2);

    int k = start;
    while (start1 <= end1 && start2 <= end2)
        reg[k++] = arr[start1] < arr[start2] ? arr[start1++] : arr[start2++];
    while (start1 <= end1)
        reg[k++] = arr[start1++];
    while (start2 <= end2)
        reg[k++] = arr[start2++];
    for (k = start; k <= end; k++)
        arr[k] = reg[k];
}

void merge_sort_pos(int arr[], const int len) {
    int reg[len];
    merge_sort_recursive_pos(arr, reg, 0, len - 1);
}