Sort an array only using recursion
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