import composit.lang.*

decl [mergesort -> list
  ([list sortme])

  decl [merge -> list                 ; synonymous with '-> {}'
    ([lists list one, list two])
    if lists.one == {} ret [lists.two]
    if lists.two == {} ret [lists.one]

    let x = [take 1 lists.one]        ; -> {} with size 1
    let y = [take 1 lists.two]        ; -> {} with size 1
    ret [x > y ? y + [merge [x + [drop 1 lists.one], lists.one]]
               : x + [merge [lists.one, y + [drop 1 lists.two]]]
    ]
  ]

  decl [split -> [list, list]
    ([list splitme])
    let si = splitme.length / 2       ; split index
    ret [[take si splitme], [drop si splitme]]
  ]

  let [decl [list left, list right]] sides = [split sortme]
  if sortme.length > 1 ret [merge [[mergesort sides.left], [mergesort sides.right]]]
  else ret sortme
]