// sortOMP.cpp : Defines the entry point for the console application.
//

#include "stdafx.h"
#include <omp.h>
#include <string>
#include <stdio.h>
#include <ctime>
#include <iostream>

int tab_size = 100000;

using namespace std;



////////////////

void merge(int *arr, int l, int m, int r)
{
    int i, j, k;
    int n1 = m - l + 1;
    int n2 = r - m;


    int *L, *R;
    L = (int*)malloc(sizeof(int*)*n1);
    R = (int*)malloc(sizeof(int*)*n2);


    for (i = 0; i < n1; i++)
        L[i] = arr[l + i];
    for (j = 0; j < n2; j++)
        R[j] = arr[m + 1 + j];

    i = 0;
    j = 0;
    k = l;
    while (i < n1 && j < n2)
    {
        if (L[i] <= R[j])
        {
            arr[k] = L[i];
            i++;
        }
        else
        {
            arr[k] = R[j];
            j++;
        }
        k++;
    }


    while (i < n1)
    {
        arr[k] = L[i];
        i++;
        k++;
    }

    while (j < n2)
    {
        arr[k] = R[j];
        j++;
        k++;
    }
    free(R); free(L);
}


void mergeSort(int *arr, int l, int r)
{
    if (l < r)
    {
        int m = l + (r - l) / 2;
        #pragma omp parallel firstprivate(m, l, r) shared(arr) //num_threads(8)
        {
            #pragma omp sections nowait
            {
                #pragma omp section
                {
                    mergeSort(arr, l, m);
                }

                #pragma omp section
                {
                    mergeSort(arr, m + 1, r);
                }
            }


        }
            merge(arr, l, m, r);

    }
}


void mergeSortSekw(int *arr, int l, int r)
{
    if (l < r)
    {

        int m = l + (r - l) / 2;
        mergeSort(arr, l, m);
        mergeSort(arr, m + 1, r);
        merge(arr, l, m, r);

    }
}

bool isAscending(int *tab, int tab_size)
{
    for (register unsigned int i = 0; i <= tab_size; i++)
    {
        if (tab[i] < tab[i - 1])
            return false;
        else
            return true;
    }
    return true;
}

void randomNumbers(int *tab, int tab_size)
{
    srand(time(0));
    register unsigned int n = tab_size;
    while (n--)
    {
        tab[n] = rand();
    }
}


int main()
{
    int *tab;
    int *t;
    srand(time(NULL));
    tab = (int*)malloc(sizeof(int*)*tab_size);
    t = (int*)malloc(sizeof(int*)*tab_size);

    randomNumbers(tab, tab_size);

    for (int i = 0; i < tab_size; i++)
    {
        t[i] = tab[i];
    }
    clock_t start = clock();
    mergeSort(tab, 0, tab_size - 1);
    clock_t end = clock();
    double elapsed_time = double(end - start) / CLOCKS_PER_SEC;
    printf("Rownolegle: %lf\n", elapsed_time);
    if (isAscending(tab, tab_size)) printf("Tablica posortowana jest prawidlowo\n");
    else printf("Tablica posortowana jest nieprawidlowo\n");
    clock_t start2 = clock();
    mergeSortSekw(t, 0, tab_size - 1);
    clock_t end2 = clock();
    double elapsed_time2 = double(end2 - start2) / CLOCKS_PER_SEC;
    printf("Sekwencyjnie: %lf\n", elapsed_time2);
    if (isAscending(t, tab_size)) printf("Tablica posortowana jest prawidlowo\n");
    else printf("Tablica posortowana jest nieprawidlowo\n");
    //
    //for (int i = 0; i < tab_size; i++)
    //{
    //  printf("Rownolegle: %d \t\t\t Sekwencyjnie: %d\n", tab[i], t[i]);
    //}


    free(tab); free(t);
    system("Pause");
    return 0;
}