jixu

object ListInsertion extends App {
  /**
   * non tail-recursive version
   */
  def insert1[T](l: List[T], v: T)(implicit ord: Ordering[T]): List[T] = l match {
    case List() => List(v)
    case x :: xs =>
      if (ord.lt(x, v)) x :: insert1(xs, v)
      else v :: l
  }