def sort[T](compare: (T, T) => Boolean)(list: List[T]): List[T] = {
  def merge(leftList: List[T], rightList: List[T]): List[T] = (leftList, rightList) match {
    case (_, Nil) => leftList
    case (Nil, _) => rightList
    case (firstLeftElement :: newLeftList, firstRightElement :: newRightList) =>
      if(compare(firstLeftElement, firstRightElement)) firstLeftElement :: merge(newLeftList, rightList)
      else firstRightElement :: merge(leftList, newRightList)
  }

  val middle = list.length / 2
  if (middle == 0) list
  else {
    val (left, right) = list.splitAt(middle)
    merge(sort(compare)(left), sort(compare)(right))
  }
}