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

int compare(const void *k1, const void *k2)
{
	int *a = (int*)k1;
	int *b = (int*)k2;
	if(*a > *b) return 1;
	if(*a == *b) return 0;
	if(*a < *b) return -1;
}

int mergesort(void *data, int count, int esize, 
	int (*compare)(const void *key1, const void *key2))
{
	void *tmp = malloc(count * esize);

	if (mgsort(data, tmp, esize, 0, count - 1, compare) < -1){
		free(tmp);
		return -1;
	}

	free(tmp);
	return 0;

}

int merge(void *data, void *tmp, int esize, int left, int right, int rightend, 
	int (*compare)(const void *key1, const void *key2))
{
	int l = left;
	int leftend = right - 1;
	int num = rightend - left + 1;
	int tmp_pos = left;
	
	while (left <= leftend && right <= rightend){
		if (compare(&data[left * esize], &data[right * esize]) < 0)
			memcpy(&tmp[(tmp_pos++) * esize], &data[(left++) * esize],esize);
		else
			memcpy(&tmp[(tmp_pos++) * esize], &data[(right++) * esize],esize);
	}
	while (left <= leftend)
		memcpy(&tmp[(tmp_pos++) * esize], &data[(left++) * esize],esize);
	while (right <= rightend)
		memcpy(&tmp[(tmp_pos++) * esize], &data[(right++) * esize],esize);
		
	memcpy(&data[l * esize], &tmp[l *esize], num*esize);
	return 0;

}

int mgsort(void *data, void *tmp, int esize, int left, int rightend, 
	int (*compare)(const void *key1, const void *key2))
{
	int center;

	if (left < rightend){
		center = (left + rightend) / 2;
		if (mgsort(data, tmp, esize, left, center, compare) < 0)
			return -1;
		if (mgsort(data, tmp, esize, center + 1, rightend, compare) < 0)
			return -1;
		if (merge(data, tmp, esize, left, center + 1, rightend, compare) < 0)
			return -1;
	}
	return 0;
}
int main(void) {
	int data[8] = {82,70,11,72,25,36,44,10};
	int i;
	int (*comp)(const void k1, const void k2) = &compare;
	mergesort(data,8,sizeof(int),comp);
	
	for(i=0;i<8;i++)
		printf("%d\n",data[i]);
	return 0;
}

I2luY2x1ZGUgPHN0ZGlvLmg+CiNpbmNsdWRlIDxzdGRsaWIuaD4KCmludCBjb21wYXJlKGNvbnN0IHZvaWQgKmsxLCBjb25zdCB2b2lkICprMikKewoJaW50ICphID0gKGludCopazE7CglpbnQgKmIgPSAoaW50KilrMjsKCWlmKCphID4gKmIpIHJldHVybiAxOwoJaWYoKmEgPT0gKmIpIHJldHVybiAwOwoJaWYoKmEgPCAqYikgcmV0dXJuIC0xOwp9CgppbnQgbWVyZ2Vzb3J0KHZvaWQgKmRhdGEsIGludCBjb3VudCwgaW50IGVzaXplLCAKCWludCAoKmNvbXBhcmUpKGNvbnN0IHZvaWQgKmtleTEsIGNvbnN0IHZvaWQgKmtleTIpKQp7Cgl2b2lkICp0bXAgPSBtYWxsb2MoY291bnQgKiBlc2l6ZSk7CgoJaWYgKG1nc29ydChkYXRhLCB0bXAsIGVzaXplLCAwLCBjb3VudCAtIDEsIGNvbXBhcmUpIDwgLTEpewoJCWZyZWUodG1wKTsKCQlyZXR1cm4gLTE7Cgl9CgoJZnJlZSh0bXApOwoJcmV0dXJuIDA7Cgp9CgppbnQgbWVyZ2Uodm9pZCAqZGF0YSwgdm9pZCAqdG1wLCBpbnQgZXNpemUsIGludCBsZWZ0LCBpbnQgcmlnaHQsIGludCByaWdodGVuZCwgCglpbnQgKCpjb21wYXJlKShjb25zdCB2b2lkICprZXkxLCBjb25zdCB2b2lkICprZXkyKSkKewoJaW50IGwgPSBsZWZ0OwoJaW50IGxlZnRlbmQgPSByaWdodCAtIDE7CglpbnQgbnVtID0gcmlnaHRlbmQgLSBsZWZ0ICsgMTsKCWludCB0bXBfcG9zID0gbGVmdDsKCQoJd2hpbGUgKGxlZnQgPD0gbGVmdGVuZCAmJiByaWdodCA8PSByaWdodGVuZCl7CgkJaWYgKGNvbXBhcmUoJmRhdGFbbGVmdCAqIGVzaXplXSwgJmRhdGFbcmlnaHQgKiBlc2l6ZV0pIDwgMCkKCQkJbWVtY3B5KCZ0bXBbKHRtcF9wb3MrKykgKiBlc2l6ZV0sICZkYXRhWyhsZWZ0KyspICogZXNpemVdLGVzaXplKTsKCQllbHNlCgkJCW1lbWNweSgmdG1wWyh0bXBfcG9zKyspICogZXNpemVdLCAmZGF0YVsocmlnaHQrKykgKiBlc2l6ZV0sZXNpemUpOwoJfQoJd2hpbGUgKGxlZnQgPD0gbGVmdGVuZCkKCQltZW1jcHkoJnRtcFsodG1wX3BvcysrKSAqIGVzaXplXSwgJmRhdGFbKGxlZnQrKykgKiBlc2l6ZV0sZXNpemUpOwoJd2hpbGUgKHJpZ2h0IDw9IHJpZ2h0ZW5kKQoJCW1lbWNweSgmdG1wWyh0bXBfcG9zKyspICogZXNpemVdLCAmZGF0YVsocmlnaHQrKykgKiBlc2l6ZV0sZXNpemUpOwoJCQoJbWVtY3B5KCZkYXRhW2wgKiBlc2l6ZV0sICZ0bXBbbCAqZXNpemVdLCBudW0qZXNpemUpOwoJcmV0dXJuIDA7Cgp9CgppbnQgbWdzb3J0KHZvaWQgKmRhdGEsIHZvaWQgKnRtcCwgaW50IGVzaXplLCBpbnQgbGVmdCwgaW50IHJpZ2h0ZW5kLCAKCWludCAoKmNvbXBhcmUpKGNvbnN0IHZvaWQgKmtleTEsIGNvbnN0IHZvaWQgKmtleTIpKQp7CglpbnQgY2VudGVyOwoKCWlmIChsZWZ0IDwgcmlnaHRlbmQpewoJCWNlbnRlciA9IChsZWZ0ICsgcmlnaHRlbmQpIC8gMjsKCQlpZiAobWdzb3J0KGRhdGEsIHRtcCwgZXNpemUsIGxlZnQsIGNlbnRlciwgY29tcGFyZSkgPCAwKQoJCQlyZXR1cm4gLTE7CgkJaWYgKG1nc29ydChkYXRhLCB0bXAsIGVzaXplLCBjZW50ZXIgKyAxLCByaWdodGVuZCwgY29tcGFyZSkgPCAwKQoJCQlyZXR1cm4gLTE7CgkJaWYgKG1lcmdlKGRhdGEsIHRtcCwgZXNpemUsIGxlZnQsIGNlbnRlciArIDEsIHJpZ2h0ZW5kLCBjb21wYXJlKSA8IDApCgkJCXJldHVybiAtMTsKCX0KCXJldHVybiAwOwp9CmludCBtYWluKHZvaWQpIHsKCWludCBkYXRhWzhdID0gezgyLDcwLDExLDcyLDI1LDM2LDQ0LDEwfTsKCWludCBpOwoJaW50ICgqY29tcCkoY29uc3Qgdm9pZCBrMSwgY29uc3Qgdm9pZCBrMikgPSAmY29tcGFyZTsKCW1lcmdlc29ydChkYXRhLDgsc2l6ZW9mKGludCksY29tcCk7CgkKCWZvcihpPTA7aTw4O2krKykKCQlwcmludGYoIiVkXG4iLGRhdGFbaV0pOwoJcmV0dXJuIDA7Cn0K