This article should be considered an independant re-implementation of all of Knuth's sorting algorithms from The Art of Programming - Vol. 3, Sorting and Searching. It provides the C code to every algorithm discussed at length in section 5.2, Internal Sorting. No explanations are provided here, the book should provide all the necessary comments. The following link is a sample implementation to confirm that everything is in working order: sknuth.c.

In order to remain as true as possible to the book, a few compromises were taken into consideration. First, the use of goto statements, which are not recommended as a good programming practice. Nevertheless, as K&R notes: "there are a few situations where gotos may find a place". Second, Knuth uses arrays which start at 1 and finish at N inclusively, which is also taken in consi- deration. Lastly, be warned that there is no error detection in the code, which is yet another terrible programming practice. Now that you have been warned, on with the code...

Comparison counting

=2; i-=1) { C3: for (j=i-1; j>=1; j-=1) { C4: if (R[i]->K < R[j]->K) COUNT[j]+=1; else COUNT[i]+=1; } } ]]>

Distribution counting

K]+=1; D4: for (i=u+1; i<=v; i+=1) COUNT[i]+=COUNT[i-1]; D5: for (j=N; j>=1; j-=1) { D6: i=COUNT[R[j]->K]; S[i]=R[j]->K; COUNT[R[j]->K]=i-1; } ]]>

Straight insertion sort

K; Rt=R[j]; S3: if (Kt>=R[i]->K) goto S5; S4: R[i+1]=R[i]; i-=1; if (i>0) goto S3; S5: R[i+1]=Rt; } ]]>

Shell's method

0; h/=2) { D2: for (j=h+1; j<=N; j+=1) { D3: i=j-h; Kt=R[j]->K; Rt=R[j]; D4: if (Kt>=R[i]->K) goto D6; D5: R[i+h]=R[i]; i-=h; if (i>0) goto D4; D6: R[i+h]=Rt; } } ]]>

List insertion

L=N; R[N]->L=0; for (j=N-1; j>=1; j-=1) { L2: p=R[0]->L; q=0; Kt=R[j]->K; L3: if (Kt<=R[p]->K) goto L5; L4: q=p; p=R[q]->L; if (p>0) goto L3; L5: R[q]->L=j; R[j]->L=p; } ]]>

Bubble sort

K>R[j+1]->K) swap(R[j],R[j+1],Rt); t=j; } B4: if (t!=0) { BOUND=t; goto B2; } ]]>

Merge exchange

=1; p=pow(2,t-(j++))) { M2: q=pow(2, t-1); r=0; d=p; M3: for (i=0; iK>R[i+d+1]->K) swap(R[i+1],R[i+d+1],Rt); } M5: if (q!=p) { d=q-p; q=q/2; r=p; goto M3; } } M6: p=p/2; if (p>0) goto M2; ]]>

Quicksort

K; Q3: i+=1; if (R[i]->KK) goto Q4; Q5: if (j<=i) { swap(R[l],R[j],Rt); goto Q7; } Q6: swap(R[i],R[j],Rt); goto Q3; Q7: if (r-j>=j-l>M) { push(j+1,r); S+=1; r=j-1; goto Q2; } if (j-l>r-j>M) { push(l,j-1); S+=1; l=j+1; goto Q2; } if (r-j>M>=j-l) { l=j+1; goto Q2; } if (j-l>M>=r-j) { r=j-1; goto Q2; } Q8: if (S) { pop(l,r); S-=1; goto Q2; } Q9: for (j=2; j<=N; j+=1) { if (R[j-1]->K > R[j]->K) { K=R[j]->K; Rt=R[j]; i=j-1; R[i+1]=R[i]; while (R[i]->K>K && i>=1) i-=1; R[i+1]=Rt; } } ]]>

Radix exchange sort

K & 1<<(b-1)) goto R6; R4: i+=1; if (i<=j) goto R3; goto R8; R5: if (!(R[j+1]->K & 1<<(b-1))) goto R7; R6: j-=1; if (i<=j) goto R5; goto R8; R7: swap(R[i],R[j+1],Rt); goto R4; R8: b-=1; if (b<0) goto R10; if (j

Straight selection sort

=2; j-=1) { S2: for (i=j, k=j-1; k>=1; k-=1) if (R[k]->K>R[i]->K) i=k; S3: swap(R[i],R[j],Rt); } ]]>

Heapsort

1) { l-=1; Rt=R[l]; Kt=R[l]->K; } else { Rt=R[r]; Kt=R[r]->K; R[r]=R[1]; r-=1; if (r==1) { R[1]=Rt; goto END; } } H3: j=l; H4: i=j; j*=2; if (jr) goto H8; H5: if (R[j]->KK) j+=1; H6: if (Kt>=R[j]->K) goto H8; H7: R[i]=R[j]; goto H4; H8: R[i]=Rt; goto H2; END: ]]>

Two-way merge

K<=y[j]->K) goto M3; else goto M5; M3: z[k]->K=x[i]->K; k+=1; i+=1; if (i<=m) goto M2; M4: while (k<=m+n || j<=n) z[k++]->K=y[j++]->K; goto END; M5: z[k]->K=y[j]->K; k+=1; j+=1; if (j<=n) goto M2; M6: while (k<=m+n || i<=m) z[k++]->K=x[i++]->K; goto END; END: ]]>

Natural two-way merge sort

K>R[j]->K) goto N8; if (i==j) { R[k]=R[i]; goto N13; } N4: R[k]=R[i]; k+=d; N5: i+=1; if (R[i-1]->K<=R[i]->K) goto N3; N6: R[k]=R[j]; k+=d; N7: j-=1; if (R[j+1]->K<=R[j]->K) goto N6; else goto N12; N8: R[k]=R[j]; k+=d; N9: j-=1; if (R[j+1]->K<=R[j]->K) goto N3; N10: R[k]=R[i]; k+=d; N11: i+=1; if (R[i-1]->K<=R[i]->K) goto N10; N12: f=0; d=-d; t=k; k=l; l=t; goto N3; N13: if (f==0) { s=1-s; goto N2; } if (s==0) for (t=1; t<=N; t+=1) { R[t]=R[t+N]; } ]]>

Straight two-way merge sort

K>R[j]->K) goto S8; S4: k=k+d; R[k]=R[i]; S5: i+=1; q-=1; if (q>0) goto S3; S6: k+=d; if (k==l) goto S13; else R[k]=R[j]; S7: j-=1; r-=1; if (r>0) goto S6; else goto S12; S8: k+=d; R[k]=R[j]; S9: j-=1; r-=1; if (r>0) goto S3; S10: k+=d; if (k==l) goto S13; else R[k]=R[i]; S11: i+=1; q-=1; if (q>0) goto S10; S12: q=p; r=p; d=-d; t=k; k=l; l=t; if (j-i

List merge sort

L=1; R[N+1]->L=2; for (i=1; i<=N-2; i++) R[i]->L=-(i+2); R[N-1]->L=R[N]->L=0; L2: s=0; t=N+1; p=R[s]->L; q=R[t]->L; if (q==0) goto END; L3: if (R[p]->K>R[q]->K) goto L6; L4: R[s]->L=set(R[s]->L,p); s=p; p=R[p]->L; if (p>0) goto L3; L5: R[s]->L=q; s=t; while (q>0) { t=q; q=R[q]->L; } goto L8; L6: R[s]->L=set(R[s]->L,q); s=q; q=R[q]->L; if (q>0) goto L3; L7: R[s]->L=p; s=t; while (p>0) { t=p; p=R[p]->L; } L8: p=-p; q=-q; if (q==0) { R[s]->L=set(R[s]->L,p); R[t]->L=0; goto L2; } else goto L3; END: ]]>

Radix list sort

It's not because it works that it's necessarily right.