#include<iostream>
#include<cstdlib>
#include<math.h>
using namespace std;

void MergeSort(int** , int, int);
void Merge(int**, int, int, int);
void duplicate_array(int**, int**, int, int);
void printout_array(int**,int,int);
void ins_sort(int**, int, int);
int main(){

int n, a_min, a_max, rseed;

cout << "Please input [n, a_min, a_max. rseed]" << endl ;
cin >> n >> a_min >> a_max >> rseed;

int** forI = new int*[1];// Building Dynamic array
int** forM = new int*[1];
for (int i = 1 ; i <= 1 ; i++){
    forI[i] = new int [n];
    forM[i] = new int [n];
}


srand(rseed); //initial randomly variable
cout << "Randomly sequence :" << endl;
for(int i = 1; i <= n; i++){                 //randomly variable between a_min & a_max
    int x = rand()%(a_max-a_min+1) + a_min;
    forI[1][i] = x;
}
cout << forI[1][10] << endl;
printout_array(forI, 1, n);
duplicate_array(forI, forM, 1, n); //copy to another array that for merge sort

cout << endl << "By insertion sort" << endl ;
ins_sort(forI, 1, n);
printout_array(forI, 1, n);

cout << endl << "By merge sort" << endl ;

MergeSort(forM, 1, n);
printout_array(forM, 1, n);

for(int i = 0; i <= n; i++){ // delete pointer array
    delete []forI[i];
    delete []forM[i];
}
delete []forI;
delete []forM;

return 0;
}

void ins_sort(int**a, int raw, int col){ //raw = 1
    int i, j, key, rec;
    for(i = 1; i <= raw; i++){         //key is additional place
        for(j = 2; j <= col; j++)
        {
            key = a[i][j];
            rec = j;                   // record position of j
            while (a[i][rec-1] < key && rec > 1 ) //the value of the left of the space is bigger than key
            {
                a[i][rec] = a[i][rec-1];          //move to left space
                rec--;
            }
            a[i][rec] = key;                     //the last space equal to key
        }
    }
}

void MergeSort(int **a, int low, int high)
{
	int mid;
	if (low < high)
	{
		mid = (low + high) / 2;
		// divide into two blocks
		MergeSort(a, low, mid);
		MergeSort(a, mid+1, high);
        //make a recursion
		// start to mergec
		Merge(a, low, high, mid);
	}
}

void Merge(int **a, int low, int high, int mid){
	// low -> middle & middle -> high have been sorted
	int i, j, k;
	int  ram[high - low + 1];
	i = low;
	k = 0;
	j = mid + 1;

	// merge into ram[]
	while (i <= mid && j <= high){   
		if (a[1][i] > a[1][j]){
			ram[k] = a[1][i];
			k++;
			i++;
		}
		else{
			ram[k] = a[1][j];
			k++;
			j++;
		}

	}
	// insert remaining function
	while (i <= mid){
		ram[k] = a[1][i];
		k++;
		i++;
	}
	while (j <= high){
		ram[k] = a[1][j];
		k++;
		j++;
	}
	// copy data from ram[] to a[][]
	for (i = low; i <= high; i++){
		a[1][i] = ram[i-low];
	}
}


void printout_array(int**A, int b, int c){//printout every single element of A[][]
    for(int i = 1; i <= b; i++){
        for(int j = 1; j <= c; j++){
            cout << A[i][j] << "  ";
        }
    }
}

void duplicate_array(int**O, int**C,int m,int n){ //copy array
    for(int i = 1; i <= m; i++)
    {
        for(int j = 0; j <= n; j++)
        {
            C[i][j] = O[i][j];
        }
    }

}