Sorting

Quicksort

Recursive

qsort = |a| ([] if len(a)==0 else
   qsort(a[1..].filter(|x| x<a[0])) + [a[0]] +
   qsort(a[1..].filter(|x| x>=a[0])))


is_sorted = |a| (0..len(a)-2).all(|i| a[i]<=a[i+1])

a = list(1..100).shuffle()
print(qsort(a))
print(is_sorted(qsort(a)))

Recursive, shorter

use math.partition

qsort = |a| [] if a==[] else qsort[a[1..]%|x| x<a[0]].chain(a[0])

Recursive, in-place

function partition(a,l,r)
   pivot = a[r]
   i = l-1
   for j in l..r-1
      if a[j] < pivot
        i = i+1
        a.swap(i,j)
     end
   end
   a.swap(i+1,r)
   return i+1
end

function quicksort(a,l,r)
   if l<r
      p = partition(a,l,r)
      quicksort(a,l,p-1)
      quicksort(a,p+1,r)
   end
end

function qsort(a)
   quicksort(a,0,len(a)-1)
end

Mergesort

msort = |a| (copy(a) if len(a)<=1 else
   merge(msort(a[1..:2]),msort(a[0..:2])))

function merge(L,R)
   y = []
   while len(L)!=0 and len(R)!=0
      y.push((L if L[-1]>R[-1] else R).pop())
   end
   return L+R+y.rev()
end

Comb sort

use math: floor

function comb_sort(a)
   gap = len(a)
   swaps = true
   while gap>1 or swaps
      gap = max(1,int(floor(gap/1.3)))
      swaps = false
      for i in 0..len(a)-1-gap
         if a[i]>a[i+gap]
            a.swap(i,i+gap)
            swaps = true
         end
      end
   end
end

By projection

# Sort a list a by comparing p(x) and p(y) for x,y in a
# where p is a projection, also called key function.
# The algorithm is also known as Schwartzian transform.

qsort = |a,rel| ([] if len(a)==0 else
   qsort(a[1..].filter(|x| rel(x,a[0])),rel)+[a[0]]+
   qsort(a[1..].filter(|x| not rel(x,a[0])),rel))

sort_by = |a,p| qsort(
   a.map(|x| [x,p(x)]), |x,y| x[1]<y[1]
).map(|x| x[0])


a = [{A=1,B=2},{A=0,B=4},{A=5,B=3},{A=3,B=1}]
print(sort_by(a,|t| t["A"]))


# built-in
print(copy(a).sort(|t| t["A"]))