#include <stdio.h>
#include <stdlib.h>
#include <string.h>
 
void merge(int L[], int p, int R[], int q, int a[]){
	int i = 0, j = 0, k = 0;
 
	while(i < p && j < q){
		if(L[i] <= R[j])
			a[k] = L[i++];
		else
			a[k] = R[j++];
		k++;
	}
	//while(i < p) a[k++] = L[i++];
	//while(j < q) a[k++] = R[j++];
	if(i == p)
		memcpy(&a[k], &R[j], sizeof(R[0]) * (q - j));
	else
		memcpy(&a[k], &L[j], sizeof(L[0]) * (p - i));
}
 
void mergesort(int a[], int n){
	int i;
	int split = n / 2;
	int *L = (int *)malloc(split);
	int *R = (int *)malloc(n - split);
 
	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);
	}
}
 
int main(int argc, char *argv[]){
	int i;
	int v[10] = {1, 3, 5, 7, 9, 2, 4, 6, 8, 10};
 
	mergesort(v, 10);
 
	for(i = 0; i < 10; i++)
		printf("%d ", v[i]);
 
	scanf("%d", &i);
	return 0;
}

I2luY2x1ZGUgPHN0ZGlvLmg+CiNpbmNsdWRlIDxzdGRsaWIuaD4KI2luY2x1ZGUgPHN0cmluZy5oPgoKdm9pZCBtZXJnZShpbnQgTFtdLCBpbnQgcCwgaW50IFJbXSwgaW50IHEsIGludCBhW10pewoJaW50IGkgPSAwLCBqID0gMCwgayA9IDA7CgoJd2hpbGUoaSA8IHAgJiYgaiA8IHEpewoJCWlmKExbaV0gPD0gUltqXSkKCQkJYVtrXSA9IExbaSsrXTsKCQllbHNlCgkJCWFba10gPSBSW2orK107CgkJaysrOwoJfQoJLy93aGlsZShpIDwgcCkgYVtrKytdID0gTFtpKytdOwoJLy93aGlsZShqIDwgcSkgYVtrKytdID0gUltqKytdOwoJaWYoaSA9PSBwKQoJCW1lbWNweSgmYVtrXSwgJlJbal0sIHNpemVvZihSWzBdKSAqIChxIC0gaikpOwoJZWxzZQoJCW1lbWNweSgmYVtrXSwgJkxbal0sIHNpemVvZihMWzBdKSAqIChwIC0gaSkpOwp9Cgp2b2lkIG1lcmdlc29ydChpbnQgYVtdLCBpbnQgbil7CglpbnQgaTsKCWludCBzcGxpdCA9IG4gLyAyOwoJaW50ICpMID0gKGludCAqKW1hbGxvYyhzcGxpdCk7CglpbnQgKlIgPSAoaW50ICopbWFsbG9jKG4gLSBzcGxpdCk7CgoJaWYobiA+IDEpewoJCWZvcihpID0gMDsgaSA8IHNwbGl0OyBpKyspCgkJCUxbaV0gPSBhW2ldOwoJCWZvcihpID0gc3BsaXQ7IGkgPCBuOyBpKyspCgkJCVJbaSAtIHNwbGl0XSA9IGFbaV07CgkJbWVyZ2Vzb3J0KEwsIHNwbGl0KTsKCQltZXJnZXNvcnQoUiwgbiAtIHNwbGl0KTsKCQltZXJnZShMLCBzcGxpdCwgUiwgbiAtIHNwbGl0LCBhKTsKCX0KfQoKaW50IG1haW4oaW50IGFyZ2MsIGNoYXIgKmFyZ3ZbXSl7CglpbnQgaTsKCWludCB2WzEwXSA9IHsxLCAzLCA1LCA3LCA5LCAyLCA0LCA2LCA4LCAxMH07CgoJbWVyZ2Vzb3J0KHYsIDEwKTsKCglmb3IoaSA9IDA7IGkgPCAxMDsgaSsrKQoJCXByaW50ZigiJWQgIiwgdltpXSk7CgoJc2NhbmYoIiVkIiwgJmkpOwoJcmV0dXJuIDA7Cn0=