Scala sort

sort.scala

import java.math.BigInteger

import scala.annotation.tailrec
import org.scalacheck.Prop.forAll

import scala.math.Ordering._

@tailrec
def sortInt[T](l1: List[T], l2: List[T] = List[T]())(implicit t : Ordering[T]): List[T] = l1 match {
  case x :: Nil =>  l2 :+ x
  case x :: y :: xs if t.gt(x,y) => sortInt(x +: xs, l2 :+ y )
  case x :: y :: xs => sortInt(y +: xs, l2 :+ x )
}


@tailrec
def sort[T](l1: List[T], l2: List[T] = List())(implicit t : Ordering[T]): List[T] = l1 match {
  case Nil => l2
  case xs =>
    val n = sortInt(xs)
    sort(n.init, n.last :: l2)
}

sortInt(List(6,5,4,3,2,1))
sortInt(List(6,1,3,4,2,1))

sort(List(6,5,4,3,2,1,7))
sort(List(6,7,12,1))
sort(List(1,2,3,4,5,6))

forAll { (l1: List[Int]) =>
  sort(l1) == l1.sorted}.check


forAll { (l1: List[String]) =>
  sort(l1) == l1.sorted}.check

forAll { (l1: List[BigInteger]) =>
  sort(l1) == l1.sorted}.check