InsertionSort.scala

def insertElement[T <% Ordered[T]](elm: T, sorted: List[T]): List[T] =
  sorted match {
    case Nil => elm :: sorted
    case head :: tail if head < elm => head :: insertElement(elm, tail)
    case _ => elm :: sorted
  }

def insertionSort[T <% Ordered[T]](list: List[T]): List[T] =
  list match {
    case Nil => list
    case head :: tail =>
      val sorted = insertionSort(tail)
      insertElement(head, sorted)
  }