#pragma clang diagnostic push
#pragma ide diagnostic ignored "openmp-use-default-none"
#include <iostream>
#include <omp.h>

using namespace std;

#define SIZE 40

void bubbleSort(int arr[], int n)
{
    int i, j;
    //omp_set_num_threads(2);
    #pragma omp for schedule(static)
    for (i = 0; i < n - 1; i++)

        // Last i elements are already in place
        for (j = 0; j < n - i - 1; j++)

            if (arr[j] > arr[j + 1])
                swap(arr[j], arr[j + 1]);
}

void insertionSort(int arr[], int n)
{
    int i, key, j;
    #pragma omp for schedule(static)
    for (i = 1; i < n; i++)
    {
        key = arr[i];
        j = i - 1;

        // Move elements of arr[0..i-1],
        // that are greater than key, to one
        // position ahead of their
        // current position
        while (j >= 0 && arr[j] > key)
        {
            arr[j + 1] = arr[j];
            j = j - 1;
        }
        arr[j + 1] = key;
    }
}

/*void merge(int arr[])
{
    //SORT 1 AND 2
    int* arr_copy = new int [SIZE];
    std::copy_n(arr, SIZE, arr_copy);

    int f = 0;
    int s = SIZE / 4;
    int i = 0;

    while ((s <= SIZE / 2) || (f <= SIZE / 2))
    {
        if(arr_copy[f] > arr_copy[s])
        {
            arr[i] = arr_copy[s];
            s++;
        }
        else
        {
            arr[i] = arr_copy[f];
            f++;
        }
        i++;
    }

    for (int j = 0; j < SIZE; j++)
        cout << arr[j] << " ";
    cout << endl;

    f = SIZE / 2;
    s = (SIZE / 4) * 3;

    while ((s <= SIZE) || (f <= SIZE))
    {
        if(arr_copy[f] > arr_copy[s])
        {
            arr[i] = arr_copy[s];
            s++;
        }
        else
        {
            arr[i] = arr_copy[f];
            f++;
        }
        i++;
    }
}*/

void Merge(int arr[], int beg, int end, int mid)
{
    int i, j, k;
    int* temp = new int [SIZE];
    std::copy_n(arr, SIZE, temp);
    i = beg;
    k = 0;
    j = mid + 1;

    while (i <= mid && j <= end)
    {
        if (arr[i] < arr[j])
        {
            temp[k] = arr[i];
            k++;
            i++;
        }
        else
        {
            temp[k] = arr[j];
            k++;
            j++;
        }
    }

    // Вставить все оставшиеся значения от i до mid temp[]
    while (i <= mid)
    {
        temp[k] = arr[i];
        k++;
        i++;
    }

    // Вставить все оставшиеся значения от j до end temp[]
    while (j <= end)
    {
        temp[k] = arr[j];
        k++;
        j++;
    }

    // Присвоить отсортированные данные в temp[] для arr[]
    for (i = beg; i <= end; i++)
    {
        arr[i] = temp[i - beg];
    }
}

int main()
{
    omp_set_nested(1);

    int* arr = new int [SIZE];

    //arr_10 = new int* [SIZE];
    srand(time(NULL));
    for (int i = 0; i < SIZE; i++)
    {
        arr[i] = rand() % 10;
        //arr_10[i] = new int[SIZE];
    }

    for (int i = 0; i < SIZE; i++)
    {
        cout << arr[i] << " ";
    }
    cout << endl;

    #pragma omp parallel num_threads(4)
    {
        //bubbleSort(arr, SIZE);
        insertionSort(arr, SIZE);
    }
    Merge(arr, 0, SIZE, SIZE / 2);
    /*Merge(arr, 0, SIZE / 2, SIZE / 4);
    Merge(arr, SIZE / 2, SIZE, (SIZE / 4) * 3);
    Merge(arr, 0, SIZE, SIZE / 2);*/

    for (int i = 0; i < SIZE; i++)
    {
        cout << arr[i] << " ";
    }
}