61 byte selection sort

13 January 2010

Here's the absolutely smallest array sorting function in C. It's written by M. Doughlas McIlroy of Darthmouth College, NH USA. It only 67 bytes long (ignoring new-line characters), which is ridiculously impressive. In the function s shown below, a is the starting address of the array, and b is the address of the last element plus one.

s(int*a,int*b)
{for(int*c=b,t;c>a;)if(t=*c--,*c>t)c[1]=*c,*c=t,c=b;}

This can be made even smaller using recursion and by inferring the type specifiers of global object declarations, which is a GCC hack. In the following function, n is the number of elements in the array a.

s(a,n)int*a;
{n-->1?s(a,n),s(a+1,n),n=*a,*a=a[1],a[n>*a]=n:0;}

The sorting function s is now only 61 bytes long!