insertionSort.scala

def sorted[S >: T](implicit ordering: Ordering[S]): List[S] = {

    /**
      * sort(4, [], [1, 2, 3, 5])
      * sort(4, [1], [2, 3, 5])
      * sort(4, [2, 1], [3, 5])
      * sort(4, [3, 2, 1], [5])
      * [3, 2, 1].reverse ++ (4 :: [5])
      */
    @tailrec
    def sort(current: T, before: List[S], after: List[S]): List[S] = {
      if (after.isEmpty || ordering.lteq(current, after.head))
        before.reverse ++ (current :: after)
      else sort(current, after.head :: before, after.tail)
    }

    /**
      * [3, 1, 4].sorted = insertionSort([3, 1, 4], []) =
      * insertionSort([1, 4], [3])
      * insertionSort([4], [1, 3])
      * insertionSort([], [1, 3, 4])
      */
    @tailrec
    def insertionSort(remaining: List[T], acc: List[S]): List[S] = {
      if (remaining.isEmpty) acc
      else insertionSort(remaining.tail, sort(remaining.head, Nil, acc))
    }

    insertionSort(this, Nil)
  }