#include <stdio.h>
#include <stdlib.h>
#define LENGTH 1000000

// --- the merging of two parts of the array a
// --- the data is merged and stores in tmp
// --- 
static void merge(int a[], int tmp[], int left, int right, int rightEnd )
{
    int leftEnd = right - 1;
    int k = left;
    int num = rightEnd - left + 1;

    while(left <= leftEnd && right <= rightEnd)
        if(a[left]<a[right])
            tmp[k++] = a[left++];
        else
            tmp[k++] = a[right++];

    while(left <= leftEnd)    // Copy rest of first half
        tmp[k++] = a[left++];

    while(right <= rightEnd)  // Copy rest of right half
        tmp[k++] = a[right++];

    // Copy tmp back
    for(int i = 0; i < num; i++, rightEnd--)
        a[rightEnd] = tmp[rightEnd];
}

// --- mergesort, a recursive function!
static void mergeSort(int a[], int tmp[], int left, int right)
{
	if( left < right )
	{
		int center = (left + right) / 2;
		mergeSort(a, tmp, left, center);
		mergeSort(a, tmp, center + 1, right);
		merge(a, tmp, left, center + 1, right);
	}
}

// --- to get started with mergesort
void mergeSort(int a[])
{
	int tmp[LENGTH];
	mergeSort(a, tmp,  0,  LENGTH - 1);
}

// --- main method to test mergesort
int main(int argc, char**argv)
{
	int a[LENGTH];// = {2, 8, 3, 5, 0};
	for (int t=0;t<LENGTH;t++){
		a[t] = rand()%100000;
	}
	mergeSort(a);
	for (int t=0;t<LENGTH;t++)
		printf("%d,",a[t]);
	return 0;
}