merge_sort.scala

def sort(list:List[Int]):List[Int] = {
  if (list.size == 1) { return list }
  val mid = list.size / 2
  val left = sort(list.take(mid))
  val right = sort(list.drop(mid))
  merge(left, right)
}

def merge(left:List[Int], right:List[Int]):List[Int]= {
  if (left.isEmpty || right.isEmpty) {
    left:::right
  } else if (left.head < right.head) {
    List(left.head):::merge(left.tail, right)
  } else {
    List(right.head):::merge(left, right.tail)
  }
}

val list = List(8,4,3,7,6,5,2,1)
println(sort(list))