gistfile1.scala

def sortCodeTrees[T <: CodeTree](trees: List[T]): List[T] = {
  val pivot = trees.length / 2
  if (pivot == 0) trees
  else {
    def merge(xs: List[T], ys: List[T]): List[T] = (xs, ys) match {
      case (Nil, ys) => ys
      case (xs, Nil) => xs
      case (x :: xs1, y :: ys1) =>
        if (weight(x) < weight(y)) x :: merge(xs1, ys)
        else y :: merge(xs, ys1)
    }
    val (front, back) = trees splitAt pivot
    merge(sortCodeTrees(front), sortCodeTrees(back))
  }
}