Scala By Example Chapter 9 Solutions - Exercise 9.1.1

Exercise 9.1.1 Provide an implementation of the missing function insert.

Insert will also be recursive, and its pretty easy to lay down the flow. Do not forget to concatenate the head after insert is applied on reduced versions of the list since we will need to return the whole inserted list and not a subset.

	object ListSort {
	def isort(xs: List[Int]): List[Int] =
	if (xs.isEmpty) Nil
	else insert(xs.head, isort(xs.tail))
	def insert(head: Int, xs: List[Int]): List[Int] =
	if (xs.isEmpty) List(head)
	else if (head > xs.head) xs.head :: insert(head, xs.tail)
	else head :: xs
	def main(args: Array[String]) {
	val l = List(6,4,8,12,1,7,22,10)
	println("List is: " + l)
	println("Sorted List is: " + isort(l))
	}
	}

view raw ListSort.scala hosted with ❤ by GitHub