isort.scala

def insertionSort(xs : List[Int]) : List[Int] = {
  xs match{
    case Nil => Nil
    case x :: xs1 => insert(x, isort(xs1))
   }
 }

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