void merge(int a[], int first, int mid, int last) {
	int* temp = new int[last + 1]; //Temporary array

	// Initialize the local indices to indicate the subarrays
	int first1 = first; // Beginning of first subarray
	int last1 = mid; // End of first subarray
	int first2 = mid + 1; // Beginning of second subarray
	int last2 = last; // End of second subarray
	// While both subarrays are not empty, copy the
	// smaller item into the temporary array
	int index = first1; // Next available location in tempArray
	while ((first1 <= last1) && (first2 <= last2))
	{
		// At this point, tempArray[first..index-1] is in order
		if (a[first1] <= a[first2])
		{
			temp[index] = a[first1];
			first1++;
		}
		else
		{
			temp[index] = a[first2];
			first2++;
		} // end if
		index++;
	}
	// Finish off the first subarray, if necessary
	while (first1 <= last1)
	{
		// At this point, tempArray[first..index-1] is in order
		temp[index] = a[first1];
		first1++;
		index++;
	} // end while
	// Finish off the second subarray, if necessary
	while (first2 <= last2)
	{
		// At this point, tempArray[first..index-1] is in order
		temp[index] = a[first2];
		first2++;
		index++;
	} // end for
   // Copy the result back into the original array
	for (index = first; index <= last; index++)
		a[index] = temp[index];
	//Release memory
	delete[]temp;
}

void sortMerge(int a[], int first, int last) {
	if (first < last) {
		// Sort each half
		int mid = first + (last - first) / 2; // Index of midpoint
		// Sort left half theArray[first..mid]
		sortMerge(a, first, mid);
		// Sort right half theArray[mid+1..last]
		sortMerge(a, mid + 1, last);
		// Merge the two halves
		merge(a, first, mid, last);
	}
}