// example node structure
typedef struct node {
	struct node *next;
	unsigned val;
} NODE;

typedef int (*CMPFN)(unsigned, unsigned);

	// example comparison function
int unsigned_cmp(unsigned lhs, unsigned rhs)
{
 if (lhs < rhs) return -1;
 if (lhs > rhs) return 1;
 return 0;
}

static void mergepair(NODE **outc, NODE **outd, NODE *a, NODE *b, CMPFN cmpfn)
{
 NODE *prev;
 NODE **other;
 other = outd;		// place for link on outd
 if (!b || cmpfn(b->val, a->val) > 0) {
	prev = a;
	a = a->next;
 } else {
	prev = b;
	b = b->next;
 }
 *outc = prev;		// put first item on outc
 for (;;) {
	NODE *nx;
		// 'prev' is the last item appended to a current list
		// 'other' is place to continue other list
		// get next item from either a or b
 	if (!b) {
		if (!a) break;	// all done
		nx = a;
		a = a->next;
	} else if (!a || cmpfn(a->val, b->val) > 0) {
		nx = b;
		b = b->next;
	} else {
		nx = a;
		a = a->next;
	}
	if (cmpfn(prev->val, nx->val) <= 0) {	// same run
		prev->next = nx;
	} else {			// end of a run
		*other = nx;		// put this item on other list
		other = &prev->next;	// swap lists
	}
	prev = nx;
 }
 *other = 0;
}

NODE *mergesortlinkedlist(NODE *inp, CMPFN cmpfn)
{
 NODE *a, *b;
 NODE **other;	// end of other list
 if (!inp || !inp->next) return inp;	// less than two items - sorted
 	// phase 1: distribute runs into a and b
 a = inp;	// start by appending first item to a
 b = 0;
 other = &b;
 while (inp->next) {
 		// inp is the last item on one list and
		// other is the place where items can be appended to the other
	NODE *nx = inp->next;
 	if (cmpfn(inp->val, nx->val) > 0) {	// wrong order - swap to other list
		*other = nx;	// nx is now the last item on the other list
		other = &inp->next;
	}
	inp = nx;
 }
 *other = 0;
 	// phase 2: merge a and b onto c and d
 for (;;) {	// Note a cannot be empty, but b can
	NODE *c, *d;
	if (!b) return a;	// already sorted
		// neither a nor b can be empty
	mergepair(&c, &d, a, b, cmpfn);
	if (!c) return d;
		// d might be empty
	a = c;	// a cannot be be empty
	b = d;	// so b might be empty
 }
}