The tiniest C sort function?

My intuition was that something really short would be really cryptic. Amazingly, the final code, reached at step 11 below, is every bit as readable as step 1. I'd venture to say more readable: step 1 has an unfair advantage of being an algorithm that everybody learns in the cradle, otherwise its logic is more complex. The path to step 11, though, passes through a pretty thorny patch around step 5.

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

HTML warning. To preserve verbatim C source, naked > symbols have been left in function definitions instead of a proper HTML escape sequence. Internet Explorer, Safari, and Firefox tolerate the lapse.

Selection sort

1. It all began with a vanilla selection sort, the precondition for which is a!=NULL&&n>=0. The only trickery here is routine: eliminating curly brackets by using commas instead of semicolons. The length is 93 bytes, excluding newlines.
   Flaw, pointed out by Bill McKeeman (who credits Steve Johnson): the function fails if a points to address 0 and n==0. This is not a problem in customary implementations where a pointer to 0 is interpreted as NULL.

   
   void sort(int*a,int n){int*b,*c,t;for(b=a+n;--b>a;)
   for(c=b;--c>=a;)if(*c>*b)t=*b,*b=*c,*c=t;}
   

2. Ditch a separate declaration by using C++/C99 loop initialization; and can variable t by reusing n. (87 bytes)

   
   void sort(int*a,int n){for(int*b=a+n,*c;--b>a;)
   for(c=b;c-->a;)if(*c>*b)n=*b,*b=*c,*c=n;}
   

3. Save the calculation of b by changing signature to sort(first,last+1). (83 bytes)

   
   void sort(int*a,int*b){for(int*c,t;--b>a;)
   for(c=b;c-->a;)if(*c>*b)t=*b,*b=*c,*c=t;}
   

4. Peter McIlroy moved the declaratins of c and t. (82 bytes)

   
   void sort(int*a,int*b){while(--b>a)
   for(int*c=b,t;c-->a;)if(*c>*b)t=*b,*b=*c,*c=t;}
   

5. Now something wild: put both loop tests in one for. (81 bytes)
   Some bootless work gets done. The inner loop test comes first, and fails the first time through. Also the if fails the first time it's executed in each iteration of the outer loop.
   Flaw: for an empty array, b==a, so the value of c in the second test is a-1. The C standard does not guarantee that a pointer value outside [a,b] will compare correctly to a, though this code will almost certainly work in practice.

   
   void sort(int*a,int*b){for(int*c=a,t;c-->a
   ||(c=--b)>a;)if(*c>*b)t=*b,*b=*c,*c=t;}
   

6. Peter takes out a common subexpression, *b, by embedding an assignment in a comparison. (80 bytes)

   
   void sort(int*a,int*b){for(int*c=a,t;c-->a
   ||(c=--b)>a;)if(*c>(t=*b))*b=*c,*c=t;}
   

7. Do away with one loop. Sweep the whole array; when an exchange happens, bump the decreasing loop index back to the top. (79 bytes)
   This turns O(N²) behavior into O(N³). But speed isn't our objective, and O(N²) is shabby itself.
   

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

8. Shorten the name. (76 bytes)

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

9. Convert from first,last+1 to first,last to get rid of a decrement operator. Use decrement and subscript [1] instead of two subscripts [-1]. (72 bytes)

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

10. Use obsolescent (pre-void) syntax. (68 bytes)

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

11. Live dangerously. Same as step 10, but with modern parameter declarations. (67 bytes)
    Actually I wrote 11 before 10, but erroneously assumed I had to revert to obsolescent syntax in order to have an int function that doesn't return a value. In fact the code is legal; the standard merely forbids use of the missing result.

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

    Recursion

12. In this (ultimately less profitable) approach the first recursive call sorts all but the first element of the array. Then if the first element isn't smallest, it's swapped with the smallest and the rest of the array is sorted again. The signature is s(first,last+1). (75 bytes)
    With two recursive calls in the body, the code may look as if its running time is O(2^N), but more detailed analysis reveals it's O(N²).
    Flaw: one element is accessed even if the array is empty.

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

13. Use obsolescent syntax. (71 bytes)
    Like step 10, this can be shortened to 70 bytes in the same way as step 11.

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

14. McKeeman recalled an ancient feature, elided type specifiers. (68 bytes)
    Alas, the trick is now illegal.

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