January 13, 2010

## 61 byte selection sort

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!