object vezbe {

  def last[T](xs: List[T]): T = xs match {
    case List()  => throw new Error("Error in last: empty list")
    case List(x) => x
    case y :: ys => last(ys)
  }
  def init[T](xs: List[T]): List[T] = xs match {
    case List()  => throw new Error("Error in init: empty list")
    case List(x) => List()
    case y :: ys => y :: init(ys)
  }
  def concat[T](xs: List[T], ys: List[T]): List[T] = xs match {
    case List()  => ys
    case z :: zs => z :: concat(zs, ys)
  }

  def reverse[T](xs: List[T]): List[T] = xs match {
    case List()  => List()
    case y :: ys => reverse(ys) ++ List(y)
  }

  def remove[T](xs: List[T], n: Int, ind: Int): List[T] = xs match {
    case List()  => xs
    case y :: ys => if (n != ind) y :: remove(ys, n, ind + 1) else ys
  }

  def removeAt[T](xs: List[T], n: Int) = remove(xs, n, 0)

  def isort(xs: List[Int]): List[Int] = xs match {
    case List()  => List()
    case y :: ys => insert(y, isort(ys))
  }
  def insert(x: Int, xs: List[Int]): List[Int] = xs match {
    case List()  => List(x)
    case y :: ys => if (x <= y) x :: xs else y :: insert(x, ys)
  }

  def msort(xs: List[Int]): List[Int] = {

    val n = xs.length / 2
    if (n == 0) xs
    else {
      def merge(xs: List[Int], ys: List[Int]): List[Int] = (xs, ys) match {
        case (xs, Nil) => xs
        case (Nil, ys) => ys
        case (x :: xs1, y :: ys1) =>
          if (x < y) x :: merge(xs1, ys) else y :: merge(xs, ys1)
      }

      val (fst, snd) = xs splitAt n
      merge(msort(fst), msort(snd))
    }

  }

  def main(args: Array[String]): Unit = {
    println("Last "+last(List(1,2,3,4,5)))
    println("Init "+init(List(1,2,3,4,5)))
    println("Concat "+concat(List(1,2,3,4,5),List(6,7,8,9,10)))
    println("Reverse "+reverse(List(1,2,3,4,5)))
    println("Remove "+removeAt(List(1,2,3,4,5),2))
    println("ISort "+isort(List(6, 2, 0, -4, 5)))
    println("MSort "+msort(List(6, 2, 0, -4, 5)))
  }
}