object MergeSort
{
  import math.Ordering

  def msort[T](xs: List[T])(lt: (T, T) => Boolean): List[T] = {
    val n = xs.length/2
    if (n==0) xs
    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 (lt(x, y)) x :: merge(xs1, ys)
          else y :: merge(xs, ys1)
        }
      }
      val (fst, snd) = xs splitAt n
      merge(msort(fst)(lt), msort(snd)(lt))
    }
  }

  /* def msortO[T](xs: List[T])(ord: Ordering[T]): List[T] = { */
  def msortO[T](xs: List[T])(implicit ord: Ordering[T]): List[T] = {
    val n = xs.length/2
    if (n==0) xs
    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 (ord.lt(x, y)) x :: merge(xs1, ys)
          else y :: merge(xs, ys1)
        }
      }
      val (fst, snd) = xs splitAt n
      /* merge(msortO(fst)(ord), msortO(snd)(ord)) */
      merge(msortO(fst), msortO(snd))
    }
  }

  def run = {
    println("MergeSort")
    val nums = List(2, 8, -2, 9, 2, 6, 0, 7, 1)
    val sorted = msort(nums)((x: Int, y: Int) => x < y)
    println(sorted)
    /* val sorted2 = msortO(nums)(Ordering.Int) */
    val sorted2 = msortO(nums)
    println(sorted2)
  }
}