object Lists
{

  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() => x :: Nil
    case y :: ys => if ( x < y ) x :: xs else y :: insert(x, ys)
  }

  def run = {
    println("Lists")
    val l = 3 :: 1 :: 8 :: 4 :: 9 :: Nil
    println(isort(l).toString)
  }
}