#include <stdio.h>
#include <stdlib.h>
#include <string.h>
 
void merge(int L[], int left_count, int R[], int right_count, int a[])
{
	int i = 0, j = 0, k = 0;
 
	while(i < left_count && j < right_count)
	{
		if(L[i] <= R[j])
			a[k] = L[i++];
		else
			a[k] = R[j++];
		k++;
	}
	if(i == left_count)
		memcpy(&a[k], &R[j], sizeof(R[0]) * (right_count - j));
	else
		memcpy(&a[k], &L[j], sizeof(L[0]) * (left_count - i));
}
 
void mergesort(int a[], int n)
{
	int i;
	int split = n / 2;
	int *L = (int *)malloc(split * sizeof(a[0]));
	int *R = (int *)malloc((n - split) * sizeof(a[0]));
 
	if(n > 1)
	{
		for(i = 0; i < split; i++)
			L[i] = a[i];
		for(i = split; i < n; i++)
			R[i - split] = a[i];
		mergesort(L, split);
		mergesort(R, n - split);
		merge(L, split, R, n - split, a);
	}
	free(L);
	free(R);
}
 
 
int main(int argc, char *argv[]){
	int i;
	const int size = 100;
	int v[size];
 
	for (i = 0; i < size; ++i)
		v[i] = i % 40;
 
 
	mergesort(v, size);
 
	for(i = 0; i < size; i++)
		printf("%d ", v[i]);
 
	return 0;
}

I2luY2x1ZGUgPHN0ZGlvLmg+CiNpbmNsdWRlIDxzdGRsaWIuaD4KI2luY2x1ZGUgPHN0cmluZy5oPgoKdm9pZCBtZXJnZShpbnQgTFtdLCBpbnQgbGVmdF9jb3VudCwgaW50IFJbXSwgaW50IHJpZ2h0X2NvdW50LCBpbnQgYVtdKQp7CglpbnQgaSA9IDAsIGogPSAwLCBrID0gMDsKCgl3aGlsZShpIDwgbGVmdF9jb3VudCAmJiBqIDwgcmlnaHRfY291bnQpCgl7CgkJaWYoTFtpXSA8PSBSW2pdKQoJCQlhW2tdID0gTFtpKytdOwoJCWVsc2UKCQkJYVtrXSA9IFJbaisrXTsKCQlrKys7Cgl9CglpZihpID09IGxlZnRfY291bnQpCgkJbWVtY3B5KCZhW2tdLCAmUltqXSwgc2l6ZW9mKFJbMF0pICogKHJpZ2h0X2NvdW50IC0gaikpOwoJZWxzZQoJCW1lbWNweSgmYVtrXSwgJkxbal0sIHNpemVvZihMWzBdKSAqIChsZWZ0X2NvdW50IC0gaSkpOwp9Cgp2b2lkIG1lcmdlc29ydChpbnQgYVtdLCBpbnQgbikKewoJaW50IGk7CglpbnQgc3BsaXQgPSBuIC8gMjsKCWludCAqTCA9IChpbnQgKiltYWxsb2Moc3BsaXQgKiBzaXplb2YoYVswXSkpOwoJaW50ICpSID0gKGludCAqKW1hbGxvYygobiAtIHNwbGl0KSAqIHNpemVvZihhWzBdKSk7CgoJaWYobiA+IDEpCgl7CgkJZm9yKGkgPSAwOyBpIDwgc3BsaXQ7IGkrKykKCQkJTFtpXSA9IGFbaV07CgkJZm9yKGkgPSBzcGxpdDsgaSA8IG47IGkrKykKCQkJUltpIC0gc3BsaXRdID0gYVtpXTsKCQltZXJnZXNvcnQoTCwgc3BsaXQpOwoJCW1lcmdlc29ydChSLCBuIC0gc3BsaXQpOwoJCW1lcmdlKEwsIHNwbGl0LCBSLCBuIC0gc3BsaXQsIGEpOwoJfQoJZnJlZShMKTsKCWZyZWUoUik7Cn0KCgppbnQgbWFpbihpbnQgYXJnYywgY2hhciAqYXJndltdKXsKCWludCBpOwoJY29uc3QgaW50IHNpemUgPSAxMDA7CglpbnQgdltzaXplXTsKCQoJZm9yIChpID0gMDsgaSA8IHNpemU7ICsraSkKCQl2W2ldID0gaSAlIDQwOwoKCgltZXJnZXNvcnQodiwgc2l6ZSk7CgoJZm9yKGkgPSAwOyBpIDwgc2l6ZTsgaSsrKQoJCXByaW50ZigiJWQgIiwgdltpXSk7CgoJcmV0dXJuIDA7Cn0=