Generically sort elements that have a concept of ordering using recursion

recursive-sort.scala

def sort[T](input: List[T])(implicit ordering: Ordering[T]): List[T] = {
  def inner(input: List[T], output: List[T]): List[T] =
    (input, output) match {
      case (Nil, out) => out

      case (head :: tail, Nil) => inner(tail, head :: Nil)

      case (iHead :: iTail, oHead :: oTail) if ordering.lteq(iHead, oHead) =>
        inner(iTail, iHead :: oHead :: oTail)

      case (iHead :: iTail, oHead :: oTail) =>
        // in the case the input head gt output head then in the output list
        // place oHead before iHead and you need to recursively call
        // inner(iHead :: Nil, oTail) to get iHead placed correctly in the
        // output list
        inner(iTail, oHead :: inner(iHead :: Nil, oTail))
    }
  inner(input, Nil)
}

sort(list)