Insertion Sort in Scala

Insertion sort is a so much simple and straightforward sorting algorithm. The pseudocode looks like following:

for j ← 2 to length[A]
    do key ← A[j]
       i ← j - 1
       while i > 0 and A[i] > key
           do A[i + 1] ← A[i]
              i ← i - 1
       A[i + 1] ← key

But do it in Scala using FP is a quite interesting experience.

Firstly, the traditional way in Scala:

def insertSort(list:Array[Int]) = {     
 var j = 1
 while(j<list.length){   
   val key = list(j)
   var i = j-1
   while(i>=0 && list(i)>key){
     list(i+1) = list(i)
     i=i-1
   }
   list(i+1)=key
   println("In the middle " + list.mkString(","))
   j=j+1
 }
 list
}

I use while rather than for, because for means more than looping.

The pure functional way requires no side-effect, which also generally means immutable and no loop.

So the first function is insert(list:List[Int], t:Int]:List[Int], which inserts a value t into a sorted list list and returns the result.

def insert(list:List[Int], t:Int):List[Int]= list match {
   case Nil => List[Int](t)
   case x::r if x > t=> t::x::r
   case x::r => x::insert(r,t)      
 }

Pattern match makes this like a breeze.

Then the sorting function:

def insertSortFp(list:List[Int])={
    (list :\ List[Int]())((a,b)=>insert(b,a))
  }

I use foldRight here just because of my laziness.