Code Review Stack Exchange is a question and answer site for peer programmer code reviews. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

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
up vote 12 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

protected by Simon Forsberg Dec 12 '15 at 13:53

Thank you for your interest in this question. Because it has attracted low-quality or spam answers that had to be removed, posting an answer now requires 10 reputation on this site (the association bonus does not count).

Would you like to answer one of these unanswered questions instead?

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