Scala mergesort

My attempt at mergesort in scala. My two previous versions weren’t great, one resulted in a stack overflow when a list > 10000 was passed (using vals) the other used vars! By switching the List[Int] to a Stream[Int] the stack overflow can be avoided, however I am not sure if this is the right thing to do. Given that I am a molecular biologist, rather than a computer scientist, I am just happy that it works as expected.

def merge(left: List[Int], right: List[Int]): Stream[Int] = {
  (left, right) match {
    case (x :: xs, y :: ys) if x < y => x #:: merge(xs, right)
    case (x :: xs, y :: ys) => y #:: merge(left, ys)
    case _ => if (left.isEmpty) right.toStream else left.toStream
  }
}
def mergesort(input: List[Int]): List[Int] = {
  input match {
    case Nil | List(_) => input
    case _ =>
      val middle:Int = input.length / 2
      val (left, right) = input splitAt middle
      merge( mergesort(left), mergesort(right) ).toList
  }
}

There is a post on Stack Overflow about mergesort (in scala), it’s short but probably worth looking at if you want better, generic implementation.

Taken from the stack overflow post linked above:

def msort[T](less: (T, T) => Boolean) (xs: List[T]): List[T] = { 
  def merge(left: List[T], right: List[T]): Stream[T] = (left, right) match {
    case (x :: xs, y :: ys) if less(x, y) => Stream.cons(x, merge(xs, right))
    case (x :: xs, y :: ys) => Stream.cons(y, merge(left, ys))
    case _ => if (left.isEmpty) right.toStream else left.toStream
  }
  val n = xs.length / 2 
  if (n == 0) xs 
  else { 
    val (ys, zs) = xs splitAt n 
    merge(msort(less)(ys), msort(less)(zs)).toList
  } 
}

// use it ...
val d = List(5.,4.,3.,2.,1.)
println( msort( (x:Double, y:Double) => x < y )(d) )

val i = List(5,4,3,2,1)
println( msort( (x:Int, y:Int) => x < y )(i) )
Advertisements

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s