Iată implementarea mea a "Sortului de îmbinare a listei" lui Knuth (Algoritmul 5.2.4L din Vol.3 al TAOCP, ediția a 2-a). Voi adăuga câteva comentarii la final, dar iată un rezumat:
La intrarea aleatorie, rulează puțin mai repede decât codul lui Simon Tatham (a se vedea răspunsul non-recursiv al lui Dave Gamble, cu un link), dar puțin mai lent decât codul recursiv al lui Dave Gamble. Este mai greu de înțeles decât oricare dintre ele. Cel puțin în implementarea mea, este necesar ca fiecare element să aibă două indicii pentru elemente. (O alternativă ar fi un indicator și un steag boolean.) Deci, probabil că nu este o abordare utilă. Cu toate acestea, un punct distinctiv este că rulează foarte rapid dacă intrarea are întinderi lungi deja sortate.
element *knuthsort(element *list)
{ /* This is my attempt at implementing Knuth's Algorithm 5.2.4L "List merge sort"
from Vol.3 of TAOCP, 2nd ed. */
element *p, *pnext, *q, *qnext, head1, head2, *s, *t;
if(!list) return NULL;
L1: /* This is the clever L1 from exercise 12, p.167, solution p.647. */
head1.next=list;
t=&head2;
for(p=list, pnext=p->next; pnext; p=pnext, pnext=p->next) {
if( cmp(p,pnext) > 0 ) { t->next=NULL; t->spare=pnext; t=p; }
}
t->next=NULL; t->spare=NULL; p->spare=NULL;
head2.next=head2.spare;
L2: /* begin a new pass: */
t=&head2;
q=t->next;
if(!q) return head1.next;
s=&head1;
p=s->next;
L3: /* compare: */
if( cmp(p,q) > 0 ) goto L6;
L4: /* add p onto the current end, s: */
if(s->next) s->next=p; else s->spare=p;
s=p;
if(p->next) { p=p->next; goto L3; }
else p=p->spare;
L5: /* complete the sublist by adding q and all its successors: */
s->next=q; s=t;
for(qnext=q->next; qnext; q=qnext, qnext=q->next);
t=q; q=q->spare;
goto L8;
L6: /* add q onto the current end, s: */
if(s->next) s->next=q; else s->spare=q;
s=q;
if(q->next) { q=q->next; goto L3; }
else q=q->spare;
L7: /* complete the sublist by adding p and all its successors: */
s->next=p;
s=t;
for(pnext=p->next; pnext; p=pnext, pnext=p->next);
t=p; p=p->spare;
L8: /* is this end of the pass? */
if(q) goto L3;
if(s->next) s->next=p; else s->spare=p;
t->next=NULL; t->spare=NULL;
goto L2;
}