3 versions of list insertion

ListInsertion.scala

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
  }

  /**
   * tail-recursive with data accumulator.
   */
  def insert2[T](l: List[T], v: T)(implicit ord: Ordering[T]): List[T] = {
    def concatReversePrefix(l: List[T], prefix: List[T]): List[T] = prefix match {
      case List() => l
      case x :: xs => concatReversePrefix(x :: l, xs)
    }
    def insertRec(l: List[T], prefix: List[T]): List[T] = l match {
      case List() => concatReversePrefix(List(v), prefix)
      case x :: xs =>
        if (ord.lt(x, v)) insertRec(xs, x :: prefix)
        else concatReversePrefix(v :: l, prefix)
    }
    insertRec(l, List())
  }

  /**
   * tail-recursive with function accumulator. 
   */
  def insert3[T](l: List[T], v: T)(implicit ord: Ordering[T]): List[T] = {
    def insertRec(l: List[T], f: (List[T]) => List[T]): List[T] = l match {
      case List() => f(List(v))
      case x :: xs =>
        if (ord.lt(x, v)) insertRec(xs, {l => f(x :: l)})
        else f(v :: l)
    }
    insertRec(l, {l => l})
  }

  val l = List(1, 2, 4, 5)
  val v = 3
  val ll = List(1, 2, 3, 4, 5)

  assert(insert1(l, v) == ll)
  assert(insert2(l, v) == ll)
  assert(insert3(l, v) == ll)
}