#include <iostream>
#include <cstdlib>
#include <ctime>
#include <climits>
void printArray(int arr[], int size);

void merge(int *arr, int left, int mid, int right)
{

	int left_size = mid - left + 1;
	int right_size = right - mid;

	int left_sub_arr[left_size], right_sub_arr[right_size];

	for (int i = 0; i < left_size; left_sub_arr[i++] = arr[left + i])
		; //i bax

	for (int j = 0; j < right_size; right_sub_arr[j++] = arr[mid + 1 + j])
		; //je ye de bax

	int i = 0, j = 0, k = left;

	while (i < left_size && j < right_size)
	{
		if (left_sub_arr[i] <= right_sub_arr[j])

			arr[k] = left_sub_arr[i++];

		else

			arr[k] = right_sub_arr[j++];

		k++;
	}

	while (i < left_size)

		arr[k++] = left_sub_arr[i++];

	while (j < right_size)

		arr[k++] = right_sub_arr[j++];
}

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

		int m = (l + r) / 2;

		mergeSort(arr, l, m);
		mergeSort(arr, m + 1, r);

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

void test_merge_sort(int size)
{     
	int *test = new int[size];

	srand(time(NULL));

	for (size_t i = 0; i < size; i++)
	{
		int r = rand() % USHRT_MAX;

		if (r % 9 == 0 || r % 31 == 0)
			r *= -1;

		test[i] = r;
	}

    std::cout<<"---------------------------------------------------------------------------------------\n";

	printArray(test, size);

    clock_t time=clock();

	mergeSort(test, 0, size - 1);

    time = clock() - time;

    std::cout<<"size:"<<size<<"\n";

    std::cout<<"time(sec):"<<(double)(double(time))/CLOCKS_PER_SEC<<"\n";

	printArray(test, size);
    
	std::cout<<"---------------------------------------------------------------------------------------\n";

	delete[] test;
}
 



int main()
{
	int size = 20;

	test_merge_sort(size);

	

	

	return 0;
}

void printArray(int arr[], int size)
{
	for (int i = 0; i < size; i++)
		std::cout << arr[i] << " ";
	std::cout << std::endl;
}