import scala.annotation.tailrec

/**
 * User: Andrei Gerasimov
 * Date: 14.11.2014
 */
object MergeSort {

  val data: List[Int] = List(5, 4, 3, 7, 9, 3, 2, 3, 1, 0, -1, 5, 6)

  def main(args: Array[String]): Unit = {
    println(sort(data))
  }

  private def sort(list: List[Int]): List[Int] = {

    @tailrec
    def merge(left: List[Int], right: List[Int], acc: List[Int]): List[Int] = (left, right) match {
      case (Nil, _) => acc.reverse ::: right
      case (_, Nil) => acc.reverse ::: left
      case (x :: xs, y :: ys) =>
        if (x < y) merge(xs, right, x :: acc)
        else merge(left, ys, y :: acc)
    }

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

}