How to change insert-sort functional code to tail recursive

Question

I recently implement the insert_sort algorithm in the functional style of programming, and it is becoming more concise and declarative. the question is how to change it to tail recursiveness, the code will throw an exception if the list size grows to 10,000.

def InsertSort(xs: List[Int]): List[Int] = xs match { case Nil => Nil case x::rest => def insert (x: Int, sorted_xs:List[Int]) :List[Int] = sorted_xs match{ case Nil => List(x) case y::ys => if (x <= y) x::y::ys else y::insert(x,ys) } insert(x,InsertSort(rest)) } 

Answer 1

Just introduced batteries:

  @tailrec def InsertSort(xs: List[Int], acc: List[Int] = Nil): List[Int] = if (xs.nonEmpty) { val x :: rest = xs @tailrec def insert(x: Int, sorted_xs: List[Int], acc: List[Int] = Nil): List[Int] = if (sorted_xs.nonEmpty) { val y :: ys = sorted_xs if (x <= y) acc ::: x :: y :: ys else insert(x,ys, acc :+ y) } else acc ::: List(x) InsertSort(rest, insert(x, acc)) } else acc 

::: and :+ will take O (n) for the default implementation of List , so it’s better to use a more appropriate collection (e.g. ListBuffer ). You can also rewrite it with foldLeft instead of explicit recursion.

Faster option ( foldLeft without :+ ):

  @tailrec def insert(sorted_xs: List[Int], x: Int, acc: List[Int] = Nil): List[Int] = if (sorted_xs.nonEmpty) { val y::ys = sorted_xs if (x <= y) acc.reverse ::: x :: y :: ys else insert(ys, x, y :: acc) } else (x :: acc).reverse scala> List(1,5,3,6,9,6,7).foldLeft(List[Int]())(insert(_, _)) res22: List[Int] = List(1, 3, 5, 6, 6, 7, 9) 

And finally, with span (as in @roterl's answer, but span works a little faster - it traverses the collection only until > x is found):

  def insert(sorted_xs: List[Int], x: Int) = if (sorted_xs.nonEmpty) { val (smaller, larger) = sorted_xs.span(_ < x) smaller ::: x :: larger } else x :: Nil scala> List(1,5,3,6,9,6,7).foldLeft(List[Int]())(insert) res25: List[Int] = List(1, 3, 5, 6, 6, 7, 9) 

Answer 2

To make the tail recursive, you must pass a sorted list as a parameter, and not build it with a return value:

 def InsertSort(xs: List[Int]): List[Int] = { @tailrec def doSort(unsortXs: List[Int], sorted_xs: List[Int]): List[Int] = { unsortXs match { case Nil => sorted_xs case x::rest => val (smaller, larger) = sorted_xs.partition(_ < x) doSort(rest, smaller ::: x :: larger) } } doSort(xs, List()) }