min_sort.par

type Nat = recursive either {
  .zero!
  .succ self
}

type List<T> = recursive either {
  .empty!
  .item(T) self
}

// sorts the argument from least to greatest
dec bubble_sort : [List<Nat>] List<Nat>
def bubble_sort = [numbers] numbers begin {
  .empty!     => .empty!
  .item(x) xs => do {
    let (min, xs)! = extract_min(x, xs)
    let sorted_xs = xs loop
  } in .item(min) sorted_xs
}

dec sort_two : [Nat, Nat] (Nat, Nat)!
def sort_two = [a, b] a begin {
  .zero!   => (.zero!, b)!
  .succ a => b {
    .zero!   => (.zero!, .succ a)!
    .succ b => let (lo, hi)! = a loop
      in (.succ lo, .succ hi)!
  }
}

dec extract_min : [Nat, List<Nat>] (Nat, List<Nat>)!
def extract_min = [x, xs] xs begin {
  .empty!     => (x, .empty!)!
  .item(y) ys => do {
    let (min, ys)! = let x = y in ys loop
    let (lo, hi)! = sort_two(x, min)
  } in (lo, .item(hi) ys)!
}