#include <iostream>
#include <cstring>	// for memcpy
using namespace std;

/* ==================================================================
 * SUBPROGRAM
 * 
 *		void merge<T>(T *t, int a, int m, int b)
 *
 * WHAT
 *   Merge two consecutive sorted subarrays into one from indices 
 *   [a,m-1] to [m,b-1].
 *
 * HOW
 *   We use a temporary array of size b-a called tmp to store
 *   the result and then we copy it to its destination in t
 *   starting at index a.
 *
 * PARAMETERS
 *
 *  @param t array of generic type T
 *  @param a index at the beginning of the array
 *  @param m index on the middle of the array
 *  @param b index at the end of the array
 *  
 *  ==================================================================
 */
template<class T>
void merge(T *t, int a, int m, int b) {
	// size of temporary array
	int tmp_size = b-a;
	// create temporary array to store sorted data
	T *tmp = new T [ tmp_size ];
	
	// indices to go through subarrays
	int i1, i2, l1, l2, k;
	
	i1 = a;
	l1 = m;
	i2 = m;
	l2 = b;
	k = 0;

	while ((i1 < l1) && (i2 < l2)) {
		if (t[i1] < t[i2]) {
			tmp[k++] = t[i1++];
		} else if (t[i2] < t[i1]) {
			tmp[k++] = t[i2++];
		} else {
			tmp[k++] = t[i1++];
			tmp[k++] = t[i2++];
		}
	}

	while (i1 < l1) {
		tmp[k++] = t[i1++];
	}

	while (i2 < l2) {
		tmp[k++] = t[i2++];
	}
	
	memcpy( &t[a], tmp, sizeof(T) * tmp_size );
	
	delete [] tmp;
	
}



/* ==================================================================
 * SUBPROGRAM
 *  
 * 		void split(T *t, int a, int b);
 *
 * WHAT
 *
 *	Recursively divide an array into two subarrays and then sort
 *  each subarray and merge the two sorted subarrays.
 *
 * HOW
 *  We divide the initial array from index a to b-1 into two 
 *  subarrays in the middle, i.e (b+a)/2. Note that we don't
 *  really divide the array, but rather use the indices to mark
 *  the begining and end of the array.
 *  If the array is of size 1, we stop and go up one level.
 *  If the array is of size 2, we sort the two values
 *  If the array is of size > 2 then we recursively divide the
 *  array in two.
 *
 * PARAMETERS
 *
 *  @param t array to sort
 *  @param a index at the beginning of the array
 *  @param b index at the end of the array  
 *	
 * ==================================================================
 */
template<class T> 
void split(T *t, int a, int b) {

	if ((b - a) <= 2) {
		if ((b - a) == 2) {
			if (t[a] > t[a+1]) {
				swap(t[a], t[a+1]);
			}
		}
	} else {
		int middle = (b+a)/2;
		
		split(t, a, middle);
		split(t, middle, b);
		
		merge(t, a, middle, b);	
	}

}


/* ==================================================================
 * SUBPROGRAM
 *
 * 		merge_sort(T *t, int size);
 *
 * WHAT
 *
 *  Perform merge sort on an array @param(t) of size @param(size)
 *
 *
 */
template<class T>
void merge_sort(T *t, int size) {

	split(t, 0, size);

}

/**
 * Programme principal
 */
int main() {
	int size = 17;
	int *tab = new int [ size ];
	
	for (int i=0; i<size; ++i) tab[i] = size-i;
	
	merge_sort(tab, size);
	
	for (int i=0; i<size; ++i) cout << tab[i] << " ";
	cout << endl;
	return EXIT_SUCCESS;
}