# Sort an array only using recursion

• Cannot call other functions (excluding itself, of course);

• Must receive an array of integers as input, and it must return the ordered array. Feel free to add other parameters as input, if you need them.

• Cannot use any kind of loop (for, while...) except recursion;

• Cannot access the internet;

• Can be overloaded if you need it.

Code-Golf here. Shortest code wins, as usual.

Happy coding!

• Most of the solution to codegolf.stackexchange.com/questions/2027/… are recursive in nature (though they work on characters rather than integers). – dmckee --- ex-moderator kitten Feb 10 '14 at 14:54
• I find 'cannot call other functions' very vague. How would one define a function? I think one could reasonably consider array-indexing a function (see e.g. Haskell's (!!)), and similarly for all other means of accessing the content of the array, but in order to sort the array one has to have a means of acessing its content. Sure, array-indexing might be one extreme, but it's a slippery slope and it's not clear to me where the line is. – FireFly Feb 11 '14 at 15:05
• In Ruby, all comparison operators (<=> and < and so on) and array operators ([] and []=) are function calls, so this task is impossible, unless I can call functions defined by the language. – kernigh May 11 '14 at 15:10

## APL (36)

{⍵≡⍬:⍬⋄(∇z/m),p,∇m/⍨~z←(p←⊃⍵)≥m←1↓⍵}


It's quicksort:

• ⍵≡⍬: if the list is equal to the empty list
• :⍬: then return the empty list
• ⋄: otherwise:
• m←1↓⍵: m is the list minus its first element
• p←⊃⍵: p (pivot) is the first element
• z←(p←⊃⍵)≥m: z is a bitmask of those values of m that are smaller than p.
• ∇m/⍨~z select the inverse of z from m (= larger numbers) , and sort it recursively
• p,: pivot
• ∇z/m: select z from m (= smaller or equal numbers) and sort it recursively
• Surely the filtering must fall foul either of calling another function or of being a loop? – Peter Taylor Feb 10 '14 at 22:14

## 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)

• are you actually returning the array, or are you just modifying it? – Justin Feb 10 '14 at 10:10
• @Quincunx, returning it. Arrays are immutable in GolfScript. The pseudocode is to show the high-level algorithm, not the low-level detail. – Peter Taylor Feb 10 '14 at 10:17

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

• Not only is foldr a function, but you seem to be defining two functions, one of which calls the other, which is also against the rules on my reading of them. This is a curious task because the requirement for recursion would seem to favour functional languages, but then their strict static typing restricts their options considerably. – Peter Taylor Feb 10 '14 at 22:13
• Actually the s in the last line is not the one defined in the first one, so it's not mutual recursion. (%) actually calls only itself. I still think functional programming languages have a huge advantage over non-functional ones, but I consider golfscript and the likes to have the necessary functional paradigm traits. Compared to your answer though, Haskell has floor and addition as functions, and default lists have two character indexing and no slicing. – shiona Feb 11 '14 at 8:32
• Actually I thought it was the other way round: it looks to me like you're defining a main function s which calls an auxiliary function %. Have I misread it? – Peter Taylor Feb 11 '14 at 9:26
• That is true, or even more accurately I pass % as a parameter to foldr in s. I admit that in the strictest sense this is not allowed, but then also the whole problem would be impossible in haskell. Only way to add elements to a list is with a concatenation binary operator (:), which is actually a function since haskell makes no difference between the two. – shiona Feb 11 '14 at 9:59

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, 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");
}


## Python 3 and 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 >.

• shuffle is definitely a function. Your old solution is better because it follows the rules. – Peter Taylor Feb 10 '14 at 22:17
• @PeterTaylor Oops, missed that rule. – Justin Feb 11 '14 at 1:03

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;
}

• You can use an arrow function - From Review – NoOneIsHere Dec 6 '16 at 23:27

### 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?(b,c=a.shift,f.(a);b>c?[c.shift]+f.([b]+c):[b]+c):a}


Explanation:

f=->(a){
a?                     # if array length is larger than 1
(
b,c=a.shift,f.(a);    # recurse on the tail of the array
b>c?               # 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
)
:a                      # array with 1 item or less - returns itself
}


# Python (78)

Edit:

def s(a,b,i):d=a[:1]>b[i:];b[i:i]=a[:d];return a and s(a[d:],b,[i+1,0][d])or b


Golfed into a one-liner by replacing if clause with Boolean d and actions that do nothing unless d is 1. Now sorts descending.

Also, used list slicing and comparisons to shorten the condition, taking advantage of the empty list being smaller than nonempty ones.

I'm still hoping for a shorter way to do [i+1,0][d]. One can do equal with i+=1;i-i*d. Operator precedence is annoying here. I'd like to do something like (i+1)*!d, where ! is some higher-precedence way to complement d. Unfortunately, 1^d is too low-precedence.

Old version: (108 chars)

def s(a,b,i):
if not a:return b
if b[i:]and a>b[i]:i+=1
else:b[i:i]=a[:1];a=a[1:];i=0
return s(a,b,i)


Call this as s(a,[],0), where a is the list to sort. In the recursion, a is the remaining list to sort and b is the part that's been sorted so far. Elements from a are pushed into b, which is maintained sorted. The index i tracks where we're looking to put the current element of a.

The line if not a:return b is horrendously wasteful. I'll try to golf it into something better when I get a chance.

# C, 114, characters

int*f(int*a,int s,int i){int*c=a+i,*d=c+1;return s>1?*c>*d&&(*c^=*d,*d^=*c,*c^=*d),i+2<s?f(a,s,i+1):f(a,s-1,0):a;}


ungolfed:

int*f(int*a,int s,int i){
int*c=a+i,*d=c+1;
return s>1
?   *c>*d
&&(*c^=*d,*d^=*c,*c^=*d), //xor-swap
i+2<s
?f(a,s,i+1) // swap the biggest number to the end of the array
:f(a,s-1,0) // last element of array is the biggest & sorted
:a;
}


Explaination
This solution uses a bubble-sort. The result of every iteration of the bubble sort is that the largest element is at the end of the array, so we don't need to sort that part anymore and reduce the size of the array after every iteration. The algorithm is finished if we get to sort an array of the length 1.

Instead of swapping using a temporary variable I'm using a xor-swap. This only works on integers.

Further Golfing:
I have to write int a lot and it wastes a lot of characters, but I can't remove these like seen in the other C solution by @LombaX, because GCC throws an error if I do.

An other thing I could do which may result in a shorter code size is using a int* parameter as output instead of the return variable. The memory for the int* output parameter could be provided by the user of the function. In this solution I wouldn't have to swap and there would probably be a better algorithm.

## C 142 bytes

Golfed

void s(int *a, int i,int j,int n)
{if((i+1)>=n)return;int t=0;if(a[i]>a[j]){t=a[i];a[i]=a[j];a[j]=t;}j++;
if((j+1)>=n){j=i+1;i++;}s(a,i,j,n);}


Ungolfed source: sorts in ascending order by swapping elements using i,j as indices.

void rec_sort(int *a, int i,int j,int n)
{
if((i+1)>=n) return;
int t=0;
if(a[i]>a[j])
{
t=a[i];
a[i]=a[j];
a[j]=t;
}
j++;
if((j+1)>=n)
{
j=i+1;
i++;
}
rec_sort(a, i, j, n);
}


# Python 2: 116

A simple bubble sort implementation

def s(l,i,d):
n=i+1
if n==len(l):return l if d else s(l,0,1)
if l[i]>l[n]:l[i:i+2]=l[n],l[i];d=0
return s(l,n,d)