Sort an array only using recursion

GolfScript (42 41)

{.,2={[.(+].~>=}*.,2>{(\S+)\S\+(\S+}*}:S;

Note: this assumes that bool{...}* is acceptable as an if without else. (Technically it's a loop). Replacing it with bool{...}{}if would add 3 chars twice.

This is a pessimisation of an already bad sorting algorithm presented in an exercise of Introduction to Algorithms, by Cormen, Leiserson, and Rivest. From memory, their version is

sort(A, off, len):
    if (len == 2) special case.
    if (len > 2):
        third = floor(len / 3)
        sort(A, off, len - third)
        sort(A, off + third, len - third)
        sort(A, off, len - third)

But all that mucking around with thirds uses characters. I do

sort(A, off, len):
    if (len == 2) special case.
    if (len > 2):
        sort(A, off, len - 1)
        sort(A, off + 1, len - 1)
        sort(A, off, len - 1)

Haskell - 51

Standard insertion sort in Haskell. I hoped I would beat golfscript for once but alas, I could not.

I could save two chars if I left out the [] from first line and require the user to pass an extra empty array as parameter, but since it makes no difference I opt not to do so.

Actually I'm not sure if foldr is allowed. It's a higher order function that sort of automates one family of recursion. If it's not drop a comment and I'll do my best to fix this.

s=foldr(%)[]
e%[]=[e]
e%(s:t)|e<s=e:s:t|e>=s=s:e%t

Javascript - 147 characters

function s(a,i,j,l){(!l)&&(i=0,j=1,l=a.length);if(i<l){(n=a[i],m=a[j],1)&&(m<n)&&(a[i]=m,a[j]=n);return (j<l)?s(a,i,j+1,l):s(a,i+1,i+2,l)}return a}

Expanded:

function s(a,i,j,l) {
  (!l) && (i=0,j=1,l=a.length)
  if(i<l) {
    if(j<l) {
      if(a[j] < a[i]) {
        var t = a[i];
        a[i] = a[j];
        a[j] = t;
      }
      return s(a,i,j+1,l);
    }
    return s(a,i+1,i+2,l);
  }
  return a;
}

Python 3 (that is, untested on Python 2) - 129 125 bytes

def s(a,i,m,o,l):
 if i<l:return s(a,i+1,[m,i][a[m]<a[i]],o,l)
 if l-o:a[o],a[m]=a[m],a[o];return s(a,o+1,-1,o+1,l)
 return a

This is called as s(list,0,-1,0,list_length).

The i<len(a) part simply runs through the array, finding the index of the max value. Then, we swap the value at that index with the current index (which I decided to call offset (o)).

This works even for an empty list and a one element list.

Note:Since it wasn't specified, I sorted descending. If the order should be ascending, replace the < at a[m]<a[i] with >.

C - 137 char (including whitespaces)

int*s(int*a,z,x,c){if(c){if(a[c-1]>a[c]){int t=a[c];a[c]=a[c-1];a[c-1]=t;}if(c>=z-1)c=-1;s(a,z,x,c+1);}if(x<z&&!c)s(a,z,x+1,1);return a;}

expanded version

int* s(int *a,z,x,c)  // this give a warning because of not specified type, but default is int so it's ok
{
    if (c)
    {
        if (a[c-1] > a[c])
        {
            int t = a[c];
            a[c] = a[c-1];
            a[c-1] = t;
        }
        if (c >= z-1)
            c = -1;

        s(a, z, x, c+1);

    }

    if (x < z && !c)
        s(a, z, x+1, 1);

    return a;
}

If you want to test it add:

int anArray[10] = {10, 1, 123,121,34,12,43,65,86,34};
s(anArray, 10, 1, 1);
printArray(anArray);

void printArray(int *arr)
{
    for(int i = 0; i < 10; i++) {
        printf("%d ", arr[i]);
        printf("\n");
    }
    printf("\n");
}

GolfScript, 47 46 characters

{.,1>{.,3<{.~>{[~\]}*}{(\S(@[\]S~@+S+}if}*}:S;

The code became quite long in the end without using all those useful operators. You can try it online.

{
  .,1>{               # if length(array)>1
    .,3<{             # if length(array)<3
      .~>             #   copy array, expand and compare
      {               #   if two elements have wrong order
        [~\]          #     swap
      }*              #   end if
    }{                # else (recursive sort)
      (\S             #   remove first element, recursively sort rest of array
      (@              #   take first element and first element (smallest) of rest of array
      [\]S            #   sort those two
      ~               #   take smaller one
      @+S             #   concat other with rest of array and sort again
      +               #   join results
    }if               # end if
  }*
}:S;

Ruby - 69 characters

f=->(a){a[1]?(b,c=a.shift,f.(a);b>c[0]?[c.shift]+f.([b]+c):[b]+c):a}

Explanation:

f=->(a){
  a[1]?                     # if array length is larger than 1
    (
      b,c=a.shift,f.(a);    # recurse on the tail of the array
      b>c[0]?               # compare the head with the first item in the sorted array
        [c.shift]+f.([b]+c) # bigger - sort the array with the original head and concat with its own head
        :[b]+c              # add the head back to the sorted array
     )
    :a                      # array with 1 item or less - returns itself
}

Python 2.x

This entry is certainly breaking some of the rules (using two 'functions' and requiring some 'setup' external to the function). This is no serious contender but I decided to post it anyway.

The method itself (including def and newlines) comes in at 71 characters.

The algorithm may not be the most efficient (pun intended).

from time import sleep as s
from thread import start_new_thread as t

def f(o,l):
 if o:
  t(lambda i,l:s(i)<l.append(i),(o.pop(0),l));f(o,l)            

# some sample code
array_to_sort=[2,4,5,2,1,7]
sorted_array=[]
f(array_to_sort, sorted_array)
s(max(array_to_sort)+1)
print sorted_array