main.hvm

// Parallel QuickSort
(Sort Nil)         = Leaf
(Sort (Cons x xs)) =
  ((Part x xs) λmin λmax
    let lft = (Sort min)
    let rgt = (Sort max)
    (Node lft x rgt))

  // Partitions a list in two halves, less-than-p and greater-than-p
  (Part p Nil)         = λt (t Nil Nil)
  (Part p (Cons x xs)) = (Push (> x p) x (Part p xs))

  // Pushes a value to the first or second list of a pair
  (Push 0 x pair) = (pair λmin λmax λp (p (Cons x min) max))
  (Push 1 x pair) = (pair λmin λmax λp (p min (Cons x max)))
  
// Generates a random list
(Rnd 0 s) = (Nil)
(Rnd n s) = (Cons s (Rnd (- n 1) (% (+ (* s 1664525) 1013904223) 4294967296)))

// Sums all elements in a concatenation tree
(Sum Leaf)         = 0
(Sum (Node l m r)) = (+ m (+ (Sum l) (Sum r)))

// Sorts and sums n random numbers
(Main n) = (Sum (Sort (Rnd (<< 1 n) 1)))