InsertSort.scala

object InsertSort {
  type T = Int

  def apply(xs: Seq[T]) = insertSort (Nil) (xs)

  def insertSort(xs: Seq[T])(ys: Seq[T]): Seq[T] =
    if (ys isEmpty) xs
    else insertSort (insertWhile (x => x >= ys.head) (ys.head) (xs)) (ys.tail)

  def insertWhile(crit: T => Boolean)(x: T)(xs: Seq[T]): Seq[T] =
    if (xs isEmpty) Seq(x)
    else {
      val (l, r) = xs splitAt (xs length / 2)
      if (crit(r.head)) insertWhile (crit) (x) (l) ++ r
      else              l ++: r.head +: insertWhile (crit) (x) (r.tail)
    }
}