#include <iostream>

using namespace std;

void printArray(int* arr, int len);
bool mSort(int *arr, int len);
void mergeArray(int *arr, int first, int mid, int last, int *temp);
void mergeSort(int *arr, int first, int last, int temp[]);

int main()
{
	int arr[] = {1, 4, 3, 10, 4, 7, 2, 5};
	int len = sizeof(arr)/sizeof(*arr);

	printArray(arr, len);
	mSort(arr, len);
	printArray(arr, len);

	cin.get();
	return 0;
}

void mergeArray(int *arr, int first, int mid, int last, int *temp)
{
	int i = first, j = mid + 1;
	int m = mid, n = last;
	int k = 0;

	while(i <= m && j <= n)
	{
		if(arr[i] <= arr[j])
			temp[k++] = arr[i++];
		else
			temp[k++] = arr[j++];
	}

	while(i <= m)
		temp[k++] = arr[i++];

	while(j <= n)
		temp[k++] = arr[j++];

	for(i = 0; i < k; i++)
		arr[i + first] = temp[i];
}

void mergeSort(int *arr, int first, int last, int *temp)
{
	if(first < last)
	{
		int mid = (first + last)/2;
		mergeSort(arr, first, mid, temp);
		mergeSort(arr, mid+1, last, temp);
		mergeArray(arr, first, mid, last, temp);
	}
}

bool mSort(int *arr, int len)
{
	int *temp = new int[len];
	if(temp == NULL)
		return false;
	mergeSort(arr, 0, len -1, temp);

	delete[] temp;
	return true;
}

void printArray(int* arr, int len)
{
	for(int i = 0; i < len; i++)
	{
		cout << arr[i] << " ";
	}
	cout << endl;
}
//cpp/8814