// 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 } }