#include "mergesrt.h"
int (*mergecompare)(void *p1, void *p2);
int mergelink;
#define getlink(adr) (*(void**)((char*)(adr)+mergelink))

static void **merge(void **head1, void **tail1, void **tail2, unsigned n1, unsigned n2)
{
	register void *p1 = *head1, *p2 = *tail1;
	for(;;) {
		if ((*mergecompare)(p1, p2) <= 0) {
			p1 = *(head1 = &getlink(*head1 = p1));
			if (--n1 == 0)
				return *head1 = p2, tail2;
		} else {
			p2 = *(head1 = &getlink(*head1 = p2));
			if (--n2 == 0)
				return *tail1 = p2, *head1 = p1, tail1;
		}
	}
}


void **mergesort(void **head, unsigned n)
{
	switch (n) {
	case 0:
		return head;
	case 1:
		return &getlink(*head);
	case 2:
		{
			register void *p1, *p2;

			p2 = getlink(p1 = *head);
			if ((*mergecompare)(p1, p2) <= 0)
				return &getlink(p2);
			getlink(p1) = getlink(*head=p2);
			return &getlink(getlink(p2) = p1);
		}
	default:
		{
			unsigned m;
			void **h2;
			n -= m = n / 2;
			h2 = mergesort(head, n);
			return merge(head,h2,mergesort(h2,m),n,m);
		}
	}
}