// Merge Sort

#include <iostream>
using namespace std;

template<class T>
void twoway(T* a, T* b, int na, int nb){
   // a[ ]: left sorted array, and resulting sorted array
   // b[ ]: right sorted array
   // na: size of a[ ]
   // nb: size of b[ ]   
	T c[na+nb];        // temp resulting array
	int iLeft = 0;     // index for left sorted array
	int iRight = 0;    // index for right sorted array
	int iMerge = 0;    // index for temp array
	while( iLeft < na && iRight < nb){
		if(a[iLeft] <= b[iRight]){
			c[iMerge] = a[iLeft];
			++iLeft;
			++iMerge;
		}else{
			c[iMerge] = b[iRight];
			++iRight;
			++iMerge;
		}
	}
	// if there are remaining in left array
	while(iLeft < na){
		c[iMerge] = a[iLeft];
		++iLeft;
		++iMerge;
	}
	// if there are remaining in right array
	while(iRight < nb){
		c[iMerge] = b[iRight];
		++iRight;
		++iMerge;
	}
	// copy temp resulting array into a[ ]
	for(int i=0 ; i < na+nb ; ++i){
		a[i] = c[i];
	}
}

// recursive merge sort
template<class T>
void MergeSort(T* a, int left, int right){
	if(left < right){
		int mid = (left + right)/2;
		MergeSort(a,left,mid);
		MergeSort(a,mid+1,right);
		twoway(a+left, a+mid+1, mid-left+1, right-mid);
	}
}

int main(){
	int unsorted[10] = {5,3,8,6,2,7,1,4,10,9};
	// print unsorted array
	for(int i=0 ; i < 10 ; ++i)
		cout << unsorted[i] << " ";
	cout << endl;
	
	MergeSort(unsorted,0,9);
	
	// print sorted array
	for(int i=0 ; i < 10 ; ++i)
		cout << unsorted[i] << " ";
	cout << endl;
	return 0;
} 


//----------------------------------------
void twoway(int a[ ], int b[ ], int c[ ], int na, int nb)
/* a[ ] and b[ ] are input sorted arrays */
/* c[ ] is the output sorted array after a[ ] and b[ ] are merged */
/* na and nb are the lengths of a[ ] and b[ ], respectively */

int merge_sort(int a[], int left, int right){   // sorting between left and right
	if(left < right){
		int mid = (left + right)/2;   // or  left + (right - left)/2;
		merge_sort(a, left, mid);
		merge_sort(a, mid+1, right);
		int c[right - left + 1];     // or  int *c = new int[right-left+1];
		twoway(a+left, a+mid+1, c, mid-left+1, right-mid);
		for(int i=0 ; i < right - left + 1 ; ++i)  
// This step is needed; otherwise, array a[ ] remains unsorted, 
// since the sorted result is stored in c[ ]
		   a[i + left] = c[i];
	}
	return 1;   // end of conquer
}

// ---------------------------------or-----------------------------
int merge_sort(int a[], int n){  // n is the length of a[ ]
	if(n==1) return 1;   // stop dividing
	merge_sort(a, n/2);
	merge_sort(a + n/2, n - n/2);
	int c[n];			 // or  int *c = new int[n];
	twoway(a, a + n/2, c, n/2, n - n/2);
	for(int i=0 ; i < n ; ++i)
// This step is needed; otherwise, array a[ ] remains unsorted, 
// since the sorted result is stored in c[ ]
		a[i] = c[i];
	return 1;          // end of conquer
}