Sort Algorithm in Scala

Question

I am going through Programming in Scala where I need some help to understand the sort example provided. The insertion sort Algorithm looks like this.

def isort(xs: List[Int]) : List[Int] = 
 if(xs.isEmpty) Nil
 else insert(xs.head, isort(xs.tail))

def insert(x: Int, xs: List[Int]) : List[Int] = 
 if(xs.isEmpty || x <= xs.head) x:: xs
 else xs.head :: insert(x, xs.tail)

To sort the List[Int] = List(4,1,3) the call will go like below.

insert(4,isort(1,3))
 insert(1,isort(3))
  insert(2,Nil)

Can some one help me from this point how the call to insert function works here.

Answer 1

insert(3, Nil) Will evaluate to List(3) as it will fall into the first if, and will be equal to 3 :: Nil.

insert(1, isort(3)) = insert(1, insert(3, Nil)) = insert(1, List(3)) Will evaluate to List(1,3), as it will also fall into the first if, because 1 is less than the head of List(3).

insert(4, isort(1,3)) = insert(4, insert(1, isort(3))) = insert(4, List(1,3)) Will fall in the second if inside the insert function, and will return 1 :: insert(4, 3). The insert(4,3) will also fall into the second if, and will return 3 :: insert(4, Nil). The insert(4, Nil) will evaluate to List(4). So in the end insert(4, List(1,3)) will return 1 :: 3 :: 4.

Answer 2

Since this book is about programming in Scala, examples try to show you the ability of Scala and try to make you familiar with its syntax. I am going to point out three different things according to your question, because I do not know which part of this example made you confused.

:: operator

Quick reminder: Scala's syntax allows you to use symbols as function name and you do not have to use . to reach these functions. Also, if a function takes one parameter, you can omit ().

:: operator simply binds to the right. Here is the illustration;

scala> 1 :: List(2, 3)
res0: List[Int] = List(1, 2, 3)

scala> List(2, 3).::(1)
res1: List[Int] = List(1, 2, 3)

If you take a look at this page, you'll see common methods and their meanings.

head & tail & last

head function returns first element of the list, tail function returns all elements except first one in the list (if list has only one element, it returns empty list List()), last function returns last element of the list;

scala> var x = List(1, 2, 3, 4, 5, 6)
scala> x.head
res2: Int = 1
scala> x.tail
res3: List[Int] = List(2, 3, 4, 5, 6)
scala> x.last
res4: Int = 6

Recursive Function

Recursive function is just a function which calls itself. For example;

def factorial(n: Int, acc: Int): Int = {
     if (n <= 0) acc
     else factorial(n - 1, n * acc)
}
scala> factorial(5, 1)
res5: Int = 120

But there is an important point about recursive functions. Our example factorial function is tail recursive. From Functional Programming in Scala;

A call is said to be 'tail position' if the caller does nothing other than return the value of the recursive call.

When you call factorial(5, 1), here are the sequence of events occurred;

factorial(5, 1)
factorial(4, 5)
factorial(3, 20)
factorial(2, 60)
factorial(1, 120)
factorial(0, 120)
120

Your example is not tail recursive, because every recursive call has to complete before binding operations. Let's take a look at sequence of events when you call isort(List(4, 1, 3));

isort(List(4, 1, 3))
insert(4, isort(List(1, 3)))
insert(4, insert(1, isort(List(3))))
insert(4, insert(1, insert(3, isort(List()))))
insert(4, insert(1, insert(3, Nil)))
insert(4, insert(1, List(3)))
insert(4, List(1, 3))
1 :: insert(4, List(3))
1 :: (3 :: insert(4, List()))
1 :: (3 :: (4 :: List()))
1 :: (3 :: List(4))
1 :: List(3, 4)
List(1, 3, 4)

For more information about recursive calls, see answer.

Answer 3

As written, insert code is recursive. It means, if x is less than head of the passed array, which is a sorted array (insert(xs.head, isort(xs.tail))) , so x inserted as a first element of the array using concatenation mark (:).

Else, the insert function called recursively on the passed array without its head, up to insert x into the proper location in the passed array.