#include <iostream>
#include <iomanip>
#include <ctime>
#include <cmath>
using namespace std;
 

// sorting algorithms
void mergeSort(int n, int s[]);
void merge(int h,int m, int u[], int v[], int s[]);
void exchangeSort(int n, int s[]);

// time checking algorithms
double cpu_time ( void );
void functionTimeCheck(string sort_type, int s[], int sLength);


 
int main() {
	
	cout << "Problem Scale : ";
	int input; // user input
	cin >> input;
	
	// create arrays
	int s_merge[input];
	int s_ex[input];
	
	// create random numbers to arrays
	srand(time(NULL));
	for(int i=0; i<input; i++){
		int rnum = rand()%1000;
		s_merge[i] = rnum;
		s_ex[i] = rnum;
	}

	// time check - merge sort
	functionTimeCheck("merge",s_merge, input);
	
	// print sorted values
	/*
	cout << "merge sort    : [";
	for(int i=0; i<input; i++){
		if(i==(input-1))
			cout << s_merge[i] << "]" << endl;
		else
			cout << s_merge[i] << ", ";
	}
	*/
	
	// time check - excahnge sort
	functionTimeCheck("exchange",s_ex, input);
	
	// print sorted values
	/*
	cout << "exchange sort : [";
	for(int i=0; i<input; i++){
		if(i==(input-1))
			cout << s_ex[i] << "]" << endl;
		else
			cout << s_ex[i] << ", ";
	}
	*/

	return 0;
	
}

// Merge Sort
void mergeSort(int n, int s[]){
    int h = n/2;
    int m = n-h;

    if(n>1) {
		int leftHalf[h];
		int rightHalf[m];
		for(int i=0;i<h;i++)
			leftHalf[i] = s[i];
		for(int i=0;i<m;i++)
			rightHalf[i] = s[h+i];

        mergeSort(h,leftHalf);
        mergeSort(m,rightHalf);
        merge(h,m,leftHalf,rightHalf,s);
	}
}

// merge
void merge(int h,int m, int u[], int v[], int s[]){
    int i=0; int j=0; int k=0;
	
    while(i<=h-1 and j<=m-1){
		if(u[i]<v[j]){
			s[k]=u[i];
			i+=1;
		}
        else{
			s[k]=v[j];
			j+=1;
		}
        
		k+=1;
	}
    if(i>h-1){
		for(int ii=j; ii<m; ii++){
			s[k]=v[ii];
			k += 1;
		}
	}
    else{
		for(int ii=i; ii<h; ii++){
			s[k]=u[ii];
			k += 1;
		}
	}
}


// Exchange Sort
void exchangeSort(int n, int s[]){
	for(int i=0; i<n-1; i++){
		for(int j=i+1; j<n; j++){
			if(s[i] > s[j]){
				int temp = s[i];
				s[i] = s[j];
				s[j] = temp;
			}
		}
	}
}

double cpu_time ( ) {
	double value;
	value = ( double ) clock ( ) / ( double ) CLOCKS_PER_SEC;
	return value;
}

// time check and print
void functionTimeCheck(string sort_type, int s[], int sLength){
	
	double atime, btime;
	
	if(sort_type == "merge"){
		atime = cpu_time();
		mergeSort(sLength,s);
		btime = cpu_time();
		cout << "merge sort    : " << -atime + btime << endl;
	}
	else if(sort_type == "exchange"){
		atime = cpu_time();
		exchangeSort(sLength,s);
		btime = cpu_time();
		cout << "exchange sort : " << -atime + btime << endl;
	}
}