Sorting

Quicksort

qsort = |a| ([] if size(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..size(a)-2).all(|i| a[i]<=a[i+1])

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



# 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,size(a)-1)
end

Mergesort

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

function merge(L,R)
  y = []
  while size(L)!=0 and size(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 = size(a)
  swaps = true
  while gap>1 or swaps
    gap = max(1,int(floor(gap/1.3)))
    swaps = false
    for i in 0..size(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 size(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"]))