current community

your communities

more stack exchange communities

Stack Exchange Inbox Reputation and Badges
tour help
Sign up ×
Code Review Stack Exchange is a question and answer site for peer programmer code reviews. It's 100% free, no registration required.
up vote 8 down vote favorite
3

I've implemented merge sort in Scala: 

 object Lunch {

  def doMergeSortExample() = {
    val values:Array[Int] = List(5,11,8,4,2).toArray
   sort(values)
    printArray(values)
  }

  def sort(array:Array[Int]) {
    if (array.length > 1 ){
      var firstArrayLength = (array.length/2)
      var first:Array[Int] = array.slice(0, firstArrayLength)
      var second:Array[Int] = array.slice(firstArrayLength, array.length)
      sort(first)
      sort(second)
      merge(array, first, second)
    }
  }

  def merge(result:Array[Int], first:Array[Int], second:Array[Int]) {
    var i:Int = 0
    var j:Int = 0
    for (k <- 0 until result.length) {
      if(i<first.length && j<second.length){
        if (first(i) < second(j)){
          result(k) = first(i)
          i=i+1
        } else {
          result(k) = second(j)
          j=j+1
        }
      }else if(i>=first.length && j<second.length){
        result(k) = second(j)
        j=j+1
      } else {
        result(k) = first(i)
        i=i+1
      }
    }
  }

  def printArray(array: Array[Int]) = {
    println(array.deep.mkString(", "))
  }

  def main(args: Array[String]) {
    doMergeSortExample();
  }

}

Could you look at this? Are there some Scala tricks to do it better, quicker, smaller or cleaner?

share|improve this question

3 Answers 3

up vote 10 down vote accepted

Just a few unsorted ideas:

  • Mergesort can be very nicely expressed using Scala's streams. In particular:

    def merge(first: Stream[Int], second: Stream[Int]): Stream[Int] =
  (first, second) match {
    case (x #:: xs, ys@(y #:: _)) if x <= y   => x #:: merge(xs, ys)
    case (xs, y #:: ys)                       => y #:: merge(xs, ys)
    case (xs, Empty)                          => xs
    case (Empty, ys)                          => ys
  }

    It'll be slower than working with arrays, but the method is much more concise, and it's completely stateless. And, it will be fully lazy - it will compute only those elements that you ask for. With such a lazy merge sort, you can sort a sequence, then ask only for the first element, and you'll get it in O(n) time instead of O(n log n).

  • Instead of splitting the input into smaller and smaller pieces and then merging them, you can split it into singletons in a single pass and then just merge those singletons. For example, create a Stream of Streams like

    def col2strstr(c: Iterable[Int]): Stream[Stream[Int]] =
  for(x <- c.toStream) yield Stream(x);

    and then merge pairs of them repeatedly. (Be sure to merge streams with the same or similar length, otherwise the process will be inefficient.)

  • This can be further improved: Instead of just splitting the input into singletons, you can split the input into non-decreasing subsequences. For example (using an informal list notation), you'd split [7,8,9,4,5,6,1,2,3] into [[7,8,9],[4,5,6],[1,2,3]]. This can dramatically reduce the number of merges. In particular, if you pass an already sorted input, it will just check that it's sorted in O(n) without doing any merge.

  • A further improvement is to look for both non-decreasing and non-increasing sequences (and reverse the non-increasing ones before merging them).

All these ideas can be seen in Haskell's sort implementation: (Haskell's lists are lazy, just like Scala's Streams.) 

sort = sortBy compare
sortBy cmp = mergeAll . sequences
  where
    sequences (a:b:xs)
      | a `cmp` b == GT = descending b [a]  xs
      | otherwise       = ascending  b (a:) xs
    sequences xs = [xs]

    descending a as (b:bs)
      | a `cmp` b == GT = descending b (a:as) bs
    descending a as bs  = (a:as): sequences bs

    ascending a as (b:bs)
      | a `cmp` b /= GT = ascending b (\ys -> as (a:ys)) bs
    ascending a as bs   = as [a]: sequences bs

    mergeAll [x] = x
    mergeAll xs  = mergeAll (mergePairs xs)

    mergePairs (a:b:xs) = merge a b: mergePairs xs
    mergePairs xs       = xs

    merge as@(a:as') bs@(b:bs')
      | a `cmp` b == GT = b:merge as  bs'
      | otherwise       = a:merge as' bs
    merge [] bs         = bs
    merge as []         = as
share|improve this answer
    
What is the role of @ operator in case (x #:: xs, ys@(y #:: _)) if x <= y => x #:: merge(xs, ys) –  Chetan Bhasin Nov 24 '14 at 15:21
    
@ChetanBhasin It's a pattern binder. If (y #:: -) matches, the expression is bound to ys. –  Petr Pudlák Nov 24 '14 at 15:53
    
I see... Thanks for the info. –  Chetan Bhasin Nov 24 '14 at 18:26
up vote 1 down vote

This is what I did a couple of years ago. I don't remember enough about mergesort or the reasons why I implemented it this way to be able to tell if this is better. It's different though. 

import scala.annotation.tailrec

def msort[T](less: (T, T) => Boolean) 
            (xs: List[T]): List[T] = { 
  @tailrec
  def merge(xs: List[T], ys: List[T], acc: List[T]): List[T] = 
    (xs, ys) match { 
      case (Nil, _) => ys.reverse ::: acc 
      case (_, Nil) => xs.reverse ::: acc
      case (x :: xs1, y :: ys1) => 
        if (less(x, y)) merge(xs1, ys, x :: acc) 
        else merge(xs, ys1, y :: acc) 
    } 
  val n = xs.length / 2 
  if (n == 0) xs 
  else { 
    val (ys, zs) = xs splitAt n 
    merge(msort(less)(ys), msort(less)(zs), Nil).reverse
  } 
}
share|improve this answer
up vote 0 down vote

This is my own implemention of a generic merge sort (note: efficiency isn't prioritized here):

  def mergeSort[T](xs: List[T])(implicit lt: (T, T) => Boolean): List[T] = {
    def merge(as: List[T], bs: List[T], acc: List[T]): List[T] = (as, bs) match {
      case (Nil, Nil) => acc
      case (Nil, ys) => acc.reverse ++ ys
      case (xs, Nil) => acc.reverse ++ xs
      case (ah :: at, bh :: bt) =>
        if (lt(ah, bh)) merge(at, bh :: bt, ah :: acc)
        else merge(ah :: at, bt, bh :: acc)
    }
    xs match {
      case Nil => Nil
      case x :: Nil => x :: Nil
      case _ =>
        val (first, second) = xs.splitAt(xs.size / 2)
        merge(mergeSort(first), mergeSort(second), Nil)
    }
  }
share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.