#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;
}