#include <stdio.h>
#include <iostream>
#include <omp.h>
#include <vector>
using namespace std;


vector<int> randomArray(int n) {
    vector<int> arr(n);
    srand(time(0));
    for (int i = 0; i < n; i++) arr[i] = rand() % 10000;
    return arr;
}

vector<int> n = randomArray(99999);

void printArr(vector<int>& arr){
//	#pragma omp parallel for
	for(int i = 0; i < arr.size(); i++){
		cout << arr[i] << "\t";

	}
	cout << endl;
}

void merge(vector<int>& arr, int left, int mid, int right){
	vector<int> temp;
	int i = left;
	int j = mid+1;
	
	while(i <= mid && j <= right){
		if(arr[i] <= arr[j]) {
			temp.push_back(arr[i]);
			i++;
		} else {
			temp.push_back(arr[j]);
			j++;
		}
		
	}

	while(j <= right){
		temp.push_back(arr[j]);
		j++;
	}

	while(i <= mid){
		temp.push_back(arr[i]);
		i++;
	}
	
	for(int k = 0; k <temp.size(); k++){
		arr[k+left] = temp[k];
	}

}


void mergeSort(vector<int>& arr, int left, int right){

	if(left >= right) return;
	
	int mid = (left + right) / 2;

	mergeSort(arr, left, mid);
	mergeSort(arr, mid+1, right);
	
	merge(arr, left, mid, right);

}


int bubble(vector<int>& arr){
//	vector<int> n = { 1, 90, 143, 22, 123};
//	printArr(n);

	for(int i = 0; i < arr.size()-1; i++){
		for(int j = 0; j < arr.size() -i -1; j++){
			if(arr[j] > arr[j+1]){
				swap(arr[j], arr[j+1]);
			}
		}
	}
	
//	printArr(n);

return 0;
}


int bubble_par(vector<int>& arr){
//      vector<int> n = { 1, 90, 143, 22, 123};
//      printArr(n);

        for(int i = 0; i < arr.size()-1; i++){
               	#pragma omp parallel for
		 for(int j = 0; j < arr.size() -i -1; j++){
                        if(arr[j] > arr[j+1]){
//                                #pragma omp critical
				{
					swap(arr[j], arr[j+1]);
                        	}
			}
                }
        }

//      printArr(n);

return 0;
}




void mergeSortP(vector<int>& arr, int left, int right){

        if(left >= right) return;

        int mid = (left + right) / 2;
	#pragma omp parallel sections
	{
        	#pragma omp section
		{
			mergeSort(arr, left, mid);
        	}


		#pragma omp section
		{
			mergeSort(arr, mid+1, right);
		}
        
	}	

	merge(arr, left, mid, right);

}




int main(){
	vector<int> n2 = n;
	vector<int> n3 = n;
	vector<int> n4 = n;
	double start, end;
	
	
//	printArr(n);
//	mergeSort(n, 0, n.size() -1);
//	bubble_par();
	start = omp_get_wtime();
	mergeSort(n, 0, n.size() -1);
	end = omp_get_wtime();

//	printArr(n);

	cout <<  1000*(end - start) << endl;

//	printArr(n2);
	start = omp_get_wtime();
	mergeSortP(n2, 0, n2.size()-1);
	end = omp_get_wtime();
//	printArr(n2);
	
	cout << 1000*(end - start) << endl;

      //  printArr(n3);
        start = omp_get_wtime();
       	bubble(n3);
        end = omp_get_wtime();
    //    printArr(n3);

        cout << 1000*(end - start) << endl;

  //      printArr(n4);
        start = omp_get_wtime();
        bubble_par(n4);
        end = omp_get_wtime();
//        printArr(n4);

        cout << 1000*(end - start) << endl;


	return 0;
}
