#include <stdio.h>
#include <stdlib.h>

void Merge(int* a, int d1, int d2)
{
	int* novi = (int*) malloc(sizeof(int) * (d1+d2));
	int i=0, j1=0, j2=0;
	while(j1 < d1 && j2 < d2)
		novi[i++] = (a[j1] <= a[d1+j2]) ? a[j1++] : a[d1+j2++];
	while(j1 < d1)
		novi[i++] = a[j1++];
	while(j2 < d2)
		novi[i++] = a[d1+j2++]; 
	for(i=0; i<d1+d2; i++)
		a[i] = novi[i];
	
	free(novi);
}

void SortMerge(int* a, int d)
{
	if(d>1)
	{
		int d1 = d/2;
		int d2 = d - d1;
		SortMerge(a, d1);
		SortMerge(a+d1, d2);
		Merge(a, d1, d2);
	}	
}

void Print(int* niz, int d)
{
     int i;
     for(i=0; i<d; i++)
     {
         printf("%d", niz[i]);      
         if(i < d-1)
             printf(", ");
         else
             putchar('\n');
     }
     
}

int main(int argc, char *argv[])
{
	int niz[] = {10, 2, 4, 1, 6, 5, 7, 8, 9, 4, 5, 6, -2, 2, 4, 8};
	Print(niz, 16);
	
	SortMerge(niz, 16);
	Print(niz, 16);
	
	system("PAUSE");	
	return 0;
}