यहां Knuth की "लिस्ट मर्ज सॉर्ट" (TAOCP के वॉल्यूम 3 से एल्गोरिदम 5.2.4L, दूसरा संस्करण) का कार्यान्वयन है। मैं अंत में कुछ टिप्पणियां जोड़ूंगा, लेकिन यहां सारांश है:
यादृच्छिक इनपुट पर, यह साइमन तथम के कोड से थोड़ा तेज़ चलता है (डेव गैंबल के गैर-रिकर्सिव उत्तर को एक लिंक के साथ देखें) लेकिन डेव गैंबल के रिकर्सिव कोड से थोड़ी धीमी है। या तो समझना मुश्किल है। कम से कम मेरे कार्यान्वयन में, प्रत्येक तत्व को तत्वों के लिए TWO पॉइंटर्स की आवश्यकता होती है। (एक विकल्प एक सूचक और एक बुलियन ध्वज होगा।) तो, यह शायद एक उपयोगी दृष्टिकोण नहीं है। हालांकि, एक विशिष्ट बिंदु यह है कि यदि इनपुट में लंबे समय तक फैला हुआ है जो पहले से क्रमबद्ध है तो यह बहुत तेज़ चलता है।
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;
}