#include <iostream>
#include <cstdlib>

#define N 10

/*
merge will combine two arrays into the sorted value
*/
void merge(int list[], int lower[], int higher[], int left, int right)
{
	//values to increment
	int i = 0, j = 0, k = 0;
	
	//while there are still variables in lower and higher
	while (i < left && j < right) 
	{
		//if the value of lower[i] <= higher[j]
		if (lower[i] <= higher[j])
		{
			//assign value to list[k]
			list[k] = lower[i]; 
			i++;	//move to next value of lower
		}
		//value of higher < lower
		else
		{
			//assign value to list[k]
			list[k] = higher[j];
			j++;	//move to next value of higher
		}

		//increment to next location in list
		k++;
	}

	//move leftover elements of lower into list
	while (i < left) 
	{
		list[k] = lower[i];
		i++;
		k++;
	}
	//move leftover elements of higher into list
	while (j < right)
	{
		list[k] = higher[j];
		j++;
		k++;
	}
}

void mergeSort(int list[], int n)
{
	int i;
	int lower[N], higher[N];
	int left, right;

	if (n < 2)
		return;   //base case

	// divide list into two array lower and higher 
	left = n / 2;   // the number of elements in lower 
	right = n - left;  // the number of elements in higher

	// move the first n/2 elements to lower 
	for (i = 0; i < left; i++) {
		lower[i] = list[i];
	}
	// move the rest to higher 
	for (i = 0; i < right; i++) {
		higher[i] = list[i + left];
	}
	// recursive calls
	mergeSort(lower, left);
	mergeSort(higher, right);

	// conquer 
	merge(list, lower, higher, left, right);

}


int main(void)
{
	int B[N] = {9, 5, 7, 1, 3, 2, 0, 4, 8, 6};

	int i = 0;
	
	//print unsorted array
	std::cout << "************** Result **************" << std::endl;
	std::cout << "The input array is:  " << std::endl;
	for (i = 0; i < N; i++)
	{
		std::cout << B[i] << " ";
	}
	std::cout << std::endl;

	// call merge sort
	mergeSort(B, N);

	/* print the sorted array */
	std::cout << "The sorted array is: " << std::endl;
	for (i = 0; i < N; i++)
	{
		std::cout << B[i] << " ";
	}
	std::cout << std::endl;

	return 0;
}