#include<stdio.h>
#include<stdlib.h>
 
struct node {
	int value;
	struct node *next;
};
 
void mergesort(struct node **n);
 
void mergesort(struct node **n) {
	struct node *n1;
	struct node *n2;
	struct node *n3;
 
	if (*n == NULL || (*n)->next == NULL) {
		return;
	}
 
	n1 = *n;
	n2 = n1->next;
 
	while (n2->next != NULL && n2->next->next != NULL) {
		n1 = n1->next;
		n2 = n2->next->next;
	}
 
	n2 = n1->next;
	n1->next = NULL;
	n1 = *n;
 
	mergesort(&n1);
	mergesort(&n2);
 
	if (n1->value >= n2->value) {
		*n = n1;
		n1 = n1->next;
	} else {
		*n = n2;
		n2 = n2->next;
	}
 
	n3 = *n;
 
	while (1) {
		if (n1 == NULL) {
			n3->next = n2;
			break;
		}
 
		if (n2 == NULL) {
			n3->next = n1;
			break;
		}
 
		if (n1->value >= n2->value) {
			n3->next = n1;
			n1 = n1->next;
		} else {
			n3->next = n2;
			n2 = n2->next;
		}
 
		n3 = n3->next;
	}
}
 
int main(void) {
	struct node *head = NULL;
	struct node *tail = NULL;
	struct node *n;
	int i;
 
	for (i = 0; i < 100; i++) {
		n = malloc(sizeof(struct node));
		n->value = (int)(rand() / (RAND_MAX + 1.0) * 1000 + 1);
		n->next = NULL;
 
		if (head == NULL) {
			head = n;
			tail = n;
		} else {
			tail->next = n;
			tail = n;
		}
	}
 
	mergesort(&head);
 
	i = 1;
	n = head;
	while (n != NULL) {
		printf("%3d : %4d\n", i, n->value);
		n = n->next;
		i++;
	}
 
	while (head != NULL) {
		n = head;
		head = head->next;
		free(n);
	}
 
	return 0;
}

I2luY2x1ZGU8c3RkaW8uaD4KI2luY2x1ZGU8c3RkbGliLmg+CgpzdHJ1Y3Qgbm9kZSB7CglpbnQgdmFsdWU7CglzdHJ1Y3Qgbm9kZSAqbmV4dDsKfTsKCnZvaWQgbWVyZ2Vzb3J0KHN0cnVjdCBub2RlICoqbik7Cgp2b2lkIG1lcmdlc29ydChzdHJ1Y3Qgbm9kZSAqKm4pIHsKCXN0cnVjdCBub2RlICpuMTsKCXN0cnVjdCBub2RlICpuMjsKCXN0cnVjdCBub2RlICpuMzsKCglpZiAoKm4gPT0gTlVMTCB8fCAoKm4pLT5uZXh0ID09IE5VTEwpIHsKCQlyZXR1cm47Cgl9CgkKCW4xID0gKm47CgluMiA9IG4xLT5uZXh0OwoJCgl3aGlsZSAobjItPm5leHQgIT0gTlVMTCAmJiBuMi0+bmV4dC0+bmV4dCAhPSBOVUxMKSB7CgkJbjEgPSBuMS0+bmV4dDsKCQluMiA9IG4yLT5uZXh0LT5uZXh0OwoJfQoJCgluMiA9IG4xLT5uZXh0OwoJbjEtPm5leHQgPSBOVUxMOwoJbjEgPSAqbjsKCgltZXJnZXNvcnQoJm4xKTsKCW1lcmdlc29ydCgmbjIpOwoJCglpZiAobjEtPnZhbHVlID49IG4yLT52YWx1ZSkgewoJCSpuID0gbjE7CgkJbjEgPSBuMS0+bmV4dDsKCX0gZWxzZSB7CgkJKm4gPSBuMjsKCQluMiA9IG4yLT5uZXh0OwoJfQoJCgluMyA9ICpuOwoJCgl3aGlsZSAoMSkgewoJCWlmIChuMSA9PSBOVUxMKSB7CgkJCW4zLT5uZXh0ID0gbjI7CgkJCWJyZWFrOwoJCX0KCQkKCQlpZiAobjIgPT0gTlVMTCkgewoJCQluMy0+bmV4dCA9IG4xOwoJCQlicmVhazsKCQl9CgkJCgkJaWYgKG4xLT52YWx1ZSA+PSBuMi0+dmFsdWUpIHsKCQkJbjMtPm5leHQgPSBuMTsKCQkJbjEgPSBuMS0+bmV4dDsKCQl9IGVsc2UgewoJCQluMy0+bmV4dCA9IG4yOwoJCQluMiA9IG4yLT5uZXh0OwoJCX0KCQkKCQluMyA9IG4zLT5uZXh0OwoJfQp9CgppbnQgbWFpbih2b2lkKSB7CglzdHJ1Y3Qgbm9kZSAqaGVhZCA9IE5VTEw7CglzdHJ1Y3Qgbm9kZSAqdGFpbCA9IE5VTEw7CglzdHJ1Y3Qgbm9kZSAqbjsKCWludCBpOwoJCglmb3IgKGkgPSAwOyBpIDwgMTAwOyBpKyspIHsKCQluID0gbWFsbG9jKHNpemVvZihzdHJ1Y3Qgbm9kZSkpOwoJCW4tPnZhbHVlID0gKGludCkocmFuZCgpIC8gKFJBTkRfTUFYICsgMS4wKSAqIDEwMDAgKyAxKTsKCQluLT5uZXh0ID0gTlVMTDsKCgkJaWYgKGhlYWQgPT0gTlVMTCkgewoJCQloZWFkID0gbjsKCQkJdGFpbCA9IG47CgkJfSBlbHNlIHsKCQkJdGFpbC0+bmV4dCA9IG47CgkJCXRhaWwgPSBuOwoJCX0KCX0KCQoJbWVyZ2Vzb3J0KCZoZWFkKTsKCQoJaSA9IDE7CgluID0gaGVhZDsKCXdoaWxlIChuICE9IE5VTEwpIHsKCQlwcmludGYoIiUzZCA6ICU0ZFxuIiwgaSwgbi0+dmFsdWUpOwoJCW4gPSBuLT5uZXh0OwoJCWkrKzsKCX0KCQoJd2hpbGUgKGhlYWQgIT0gTlVMTCkgewoJCW4gPSBoZWFkOwoJCWhlYWQgPSBoZWFkLT5uZXh0OwoJCWZyZWUobik7Cgl9CgkKCXJldHVybiAwOwp9