## Saturday, August 10, 2013

### Scala, lists, vectors and mergesort

Today I noticed the following example of mergesort, quoted in the online book "Scala by example" (9.3 Example: Merge sort, page 69):

def msort[A](less: (A, A) => Boolean)(xs: List[A]): List[A] = {
```    def merge(xs1: List[A], xs2: List[A]): List[A] =
if (xs1.isEmpty) xs2
else if (xs2.isEmpty) xs1
val n = xs.length/2
if (n == 0) xs
else merge(msort(less)(xs take n), msort(less)(xs drop n))
}
```

Further the authors say that the complexity of this algorithm is O(N log (N)), which makes it an attractive option for sorting lists.

Being in an inquisitive mood, I couldn't help wondering how big can in practice be a list sorted with such algorithm. (My current machine is 64-bit Ubuntu with 6 GB RAM and 8 cores)

So here we go.

scala> import scala.util.Random
scala> val randomNums = Seq.fill(1000)(Random.nextInt)
scala> msort((x:Int,y:Int)=>x<y)(randomNums.toList)

res27: List[Int] = List(-2145589793, -2143814602, -2143330861, -2142630038, -2136184047, -2135476301, -2132371275, -2129131922, -2123018872, -2120069375, -2118819114, -2117572993, -2112618055, -2102489605, -2096417279, -2095978655, -2095806565, -2087860343, -2087105558, -2085005596, -2083360810, -2077234330, -2065393243, -2058765966, -2056823240, -2053145149, -2047696716, -2044737011, -1847777706, -18259...

OK, for 1000 elements it works, for 10000 it works too. But let's push one more order of magnitude...

scala> val randomNums = Seq.fill(100000)(Random.nextInt).toList
randomNums: List[Int] = List(186865346, 638415825, -637620864, 220723809, -1536234831, 1710286185, 126091472, -1621728642, -1819749330, -294195052, -613979926, 1278841478, -111715804, -1953497441, 1891679544, 582175290, 1555531003, -430520072, 652471392, 1211722008, -112446234, -1900260621, 2058382521, 564201400, -1225275015, 2069052362, 797097978, 1077363576, 1469066877, -303059738, -166855116, -1876385701, 285630983, -1956550564, -1991336959, -1713232594, -868759609, -723403847, -282664963, 1965397484, 1563483549, -618177790, -297223307, -197365661, -703715983, 28207094, -1793590690, 374050582, 992041027, -1931269739, -932512120, -1551657371, 1523463808, -742246427, -1665172973, 50892779, -286029416, -1654054925, -874783455, -1825744857, -571856180, 289326103, -215127347, -1488600483,...
scala> msort((x:Int,y:Int)=>x<y)(randomNums)
java.lang.StackOverflowError
at .merge\$1(<console>:20)
at .merge\$1(<console>:22)
at .merge\$1(<console>:20)
at .merge\$1(<console>:20)
at .merge\$1(<console>:20)
at .merge\$1(<console>:20)
at .merge\$1(<console>:22)
...
Oi wei, we ran out of stack!
The reasons are obvious: this line of code

means that all the time while you are busy merging the partial lists, there are orphan elements hanging around, waiting until they are allowed to be the head. And the stack isn't made of rubber!

Well... there is some sport, of course, could we make it at least work? Using the tail recursion, perhaps? (If you have forgotten, tail recursion happens when the recursive function ends with calling itself. Then the compiler can be smart enough to make a cycle instead of the sequence of the recursive calls, at least if you ask it politely :) )
```
import scala.annotation.tailrec
...
@tailrec
def merge(xs1: List[A], xs2: List[A]): List[A] =
if (xs1.isEmpty) xs2
else if (xs2.isEmpty) xs1
```

However, this won't compile, and rightly so:

[error]
<filename>: could not optimize @tailrec annotated method merge: it contains a recursive call not in tail position
[error] else xs2.head :: merge(xs1, xs2.tail)

Ah right. Operator :: is right associative, that means it's called after merge(arg1, arg2) was called, therefore tail recursion isn't possible.

Well, without further ado, that is the variant I have ended up with. It worked in the sense that it didn't break - there was now a cycle - but for the list with 100000 elements it took about 5 minutes to do the sorting!

import scala.math.Ordering.Implicits._
import scala.util.Random
import scala.annotation.tailrec

object Sorting {
def less[T:Ordering](x:T,y:T) = x<y
@tailrec
def merge[A:Ordering ](xs0: List[A], xs1: List[A], xs2: List[A]): List[A] =
if (xs1.isEmpty) if (xs0 == Nil) xs2 else xs0 ::: xs2
else if (xs2.isEmpty) if (xs0 == Nil) xs1 else xs0 ::: xs1
else merge(xs0 :+ xs2.head, xs1, xs2.tail)

def msort[A:Ordering](xs: List[A]): List[A] = {
val n = xs.length/2
if (n == 0) xs
else merge(List[A](), msort(xs take n), msort(xs drop n))
}
def checkSorted[A:Ordering](x:A, xs:List[A]):Boolean = xs match {
case Nil => true
}
def test(size:Int, printAll:Boolean = true) = {
val randomNums = Seq.fill(size)(Random.nextInt).toList
val sorted = msort(randomNums)
if (printAll) println(sorted)
}
}

The reason why this code is slow is in the fact that now we have added the accumulator, and we want to add elements to the end of it. However, List (as also mentioned here) only guarantees the quick access to the head - the complexity of accessing the last element would be proportional to the size of the list!

So is there anything to do to make it faster, without trying hard to imagine some other algorithm? My solution was to use Vectors instead of Lists.

object Sorting {
def less[T:Ordering](x:T,y:T) = x<y
@tailrec
def merge[A:Ordering ](xs0: Vector[A], xs1: Vector[A], xs2: Vector[A]): Vector[A] =
if (xs1.isEmpty) if (xs0 == Nil) xs2 else xs0 ++ xs2
else if (xs2.isEmpty) if (xs0 == Nil) xs1 else xs0 ++ xs1
else merge(xs0 :+ xs2.head, xs1, xs2.tail)

def msort[A:Ordering](xs: Vector[A]): Vector[A] = {
val n = xs.length/2
if (n == 0) xs
else merge(Vector[A](), msort(xs take n), msort(xs drop n))
}
def checkSorted[A:Ordering](x:A, xs:List[A]):Boolean = xs match {
case Nil => true
}
def test(size:Int, printAll:Boolean = true) = {
val randomNums = Seq.fill(size)(Random.nextInt).toVector
val sortedVec = msort(randomNums)
if (printAll) println(sortedVec)
val sorted = sortedVec.toList