quicksort — functional quicksort on lists

Classic quicksort: split the tail of the list into "less-or-equal" and "greater than" the pivot using two named filter functions, recurse, then append the sorted parts.

Source (examples/quicksort.rail):

-- quicksort.rail — functional quicksort on lists
--
-- Demonstrates: recursion, list operations (head, tail, cons, append, length),
--               custom filter functions, join/show for output

showNum x = show x

filterLeq xs pivot =
  if length xs == 0 then []
  else if head xs <= pivot then cons (head xs) (filterLeq (tail xs) pivot)
  else filterLeq (tail xs) pivot

filterGt xs pivot =
  if length xs == 0 then []
  else if head xs > pivot then cons (head xs) (filterGt (tail xs) pivot)
  else filterGt (tail xs) pivot

qsort xs =
  if length xs <= 1 then xs
  else let p = head xs
       let rest = tail xs
       let lo = filterLeq rest p
       let hi = filterGt rest p
       append (qsort lo) (cons p (qsort hi))

main =
  let xs = [3, 6, 1, 8, 2, 9, 4, 7, 5]
  let _ = print "Input:"
  let _ = print (join " " (map showNum xs))
  let _ = print "Sorted:"
  let _ = print (join " " (map showNum (qsort xs)))
  let _ = print ""
  let big = [42, 17, 93, 5, 28, 64, 11, 79, 33, 50, 2, 88]
  let _ = print "Larger list:"
  let _ = print (join " " (map showNum (qsort big)))
  0

Run:

./rail_native run examples/quicksort.rail

Output:

Input:
3 6 1 8 2 9 4 7 5
Sorted:
1 2 3 4 5 6 7 8 9

Larger list:
2 5 11 17 28 33 42 50 64 79 88 93