4
\$\begingroup\$

I have implemented a sortmerge in Scala in one single function. I would like to have it reviewed, so that I can have it well organized, and it is then doing what needs to do.

val a = Array(5, 4, 1, 8, 7, 2, 6, 3)


def mergeSort(a: Array[Int]): Array[Int] = {
  val size = a.length

  if (size == 1) {
    return a
  }
  val a1 = new Array[Int](size / 2)
  val a2 = new Array[Int](size / 2)

  val upTo = (a.length / 2) - 1
  for (i <- 0 to upTo) {
    a1(i) = a(i)
  }
  var pos = 0
  for (i <- upTo+1 to a.length - 1) {
    a2(pos) = a(i)
    pos += 1
  }

  val aR1 = mergeSort(a1)
  val aR2 = mergeSort(a2)
  val aFinalR = new Array[Int](size)

  var i = 0
  var j = 0
  var upBoundR1 = false;
  var upBoundR2 = false;
  for (k <- 0 to aFinalR.length - 1) {
    if (aR1(i) < aR2(j) && !upBoundR1) {
      aFinalR(k) = aR1(i)
      if (i == aR1.length - 1) {
        upBoundR1 = true
      }
      else{
        i = i+1
      }
    } else if (aR2(j) < aR1(i) && !upBoundR2) {
      aFinalR(k) = aR2(j)
      if(j == aR2.length  -1) {
        upBoundR2 = true
      }
      else{
        j = j+1
      }
    } else {
      if(upBoundR1) {
        aFinalR(k) = aR2(j)
        j = if (j == aR2.length - 1) j else j + 1
      } else {
        aFinalR(k) = aR1(i)
        i = if (i == aR1.length - 1) j else i + 1
      }
    }
  }
  return aFinalR
}


val r = mergeSort(Array(1,2,5,4,3,7))

How can I use this function for arrays of different sizes?

And how can I clean up this code a bit more, I feel like the code is a little too big.

I would like to avoid the use of pattern matching, but rather, intentionally sort Arrays by iterating through them, at the same time, I would like to do a canonical merge sort, how can I get there?

\$\endgroup\$
  • 2
    \$\begingroup\$ If you don't want to do things the idiomatic Scala way, then you will have to make it very clear why you want to do that, which till now you haven't. The coding styles are idiomatic for a reason, don't try to shoehorn stuff into where they aren't very welcome. \$\endgroup\$ – Tamoghna Chowdhury Nov 24 '16 at 19:03
5
\$\begingroup\$

Let me very clear here: I don't like what you have done and I don't like what you want to do.

With that out of the way, however, let me explain myself:

Scala is heavily inspired by the functional paradigm, which favors logic development by composition of smaller functions into larger ones and using a more declarative style, where you tell the computer "what" you want to do, not "how" you want to do it., unlike primarily imperative languages like C/C++/C#/Java.

Following the functional paradigm leads to more concise, verifiable and readable code (in most cases) over equivalent imperative implementations.

Pattern matching and recursion are especially important in the functional paradigm, where uncontrolled global mutable state is an anathema.

Yet, in Scala, you want to to do it the imperative way. Very well, Scala allows you to do it. However, should you? Most wouldn't think so.

Now on to the code review.

Observations

All you have done is hard-inlined the merge of mergeSort into the mergeSort() function itself.

If function call overheads are your primary concern for doing this, you probably shouldn't be using Scala. You should be using C/C++.

However, you're using Scala. So split it up. Write the merging function as a separate function, following the Single Responsibility Principle (SRP).

You have said that you don't want to pattern match and want to loop over the elements of the array, when you very well know merge sort in Scala can be implemented as a one-liner. That is kind of like taking the engine out of your car because you want to ride it like it's a quadricycle (or motorbike to bicycle, whichever makes more sense).

  1. Horrible variable naming. aR1 and aR2 mean what, exactly? Why not leftSubArray and rightSubArray? More typing, yes, but that much clearer.

Suggestions

  1. Write Scala like Scala should be written. You will be benefiting any other who will have to work on your code later. You will be benefiting yourself if you ever look at this code after you've gained more experience.

  2. Use an IndexedSeq instead of an Array. Updates will not be in-place if you use the IndexedSeq object's apply() method (which returns a scala.Vector in Scala 2.11), as this is an immutable data structure unlike an Array. However, a Vector gets you type covariance. To get around the immutability in your design, keep the Vector as a var and reassign the result of any calls to updated() on it to itself. This is a first step on the path of functional-ness.

  3. The Scala Predef and standard libraries have a lot of nice functions for you to exploit instead of explicitly looping over everything. You could try foreach, map and flatMap to help. There's also the handly sequence concatenation operator ++. There's also handy comparison functions like orderBy, and something which invalidates the need for what you are trying to do, sorted and sortBy

  4. Try until instead of to for ranges. until will return a half-open interval in comparison to the closed interval returned by to. That is:

    0 to 10 = [0,1,2,3,4,5,6,7,8,9,10]
    0 until 10 = [0,1,2,3,4,5,6,7,8,9]
    

    That should help get rid of some of the ugly -1s.

  5. Even imperative merging isn't that complicated. Try the following, it should help:

    def merge(arr: Array[Int], low: Int, mid: Int, high: Int): Array[Int] = {
        /*[low..mid..high), high is exclusive*/
        var (i, j, k) = (0, 0, 0)
        val (leftLength, rightLength) = (mid - low + 1, high - mid)
        /* create temp arrays */
        val (leftArr, rightArr) = Array(leftLength), Array(rightLength)
        /* Copy data to temp arrays leftArr and rightArr */
        arr.copyToArray(leftArr, low, leftLength)
        arr.copyToArray(rightArr, mid, rightLength)
        /* Merge the temp arrays back into arr(l..r)*/
        i = 0; // Initial index of first subarray
        j = 0; // Initial index of second subarray
        k = l; // Initial index of merged subarray
        while (i < leftLength && j < rightLength){
            if (leftArr(i) <= rightArr(j)){
                arr(k) = leftArr(i);
                i+=1;
            }
            else{
                arr(k) = rightArr(j);
                j+=1;
            }
            k+=1;
        }
        /* Copy the remaining elements of leftArr, if there
           are any */
        while (i < leftLength){
            arr(k) = leftArr(i);
            i+=1;
            k+=1;
        }
        /* Copy the remaining elements of rightArr, if there
           are any */
        while (j < rightLength){
            arr(k) = rightArr(j);
            j+=1;
            k+=1;
        }
        arr
    }
    

I use Array instead of IndexedSeq in the above example as I need the intrinsic mutability of arrays in the presented method. It could have been written using IndexedSeq and assignment updates instead, but that would make the intent of the code a little less clear IMHO.

The functional one can be as simple as:

    def merge(left: IndexedSeq[Int], right: IndexedSeq[Int]): IndexedSeq[Int] = 
        (left ++ right).sorted

The implementation without sorted() involves pattern matching, take a look here for details (especially @Shadowlands' answer for one without explicit pattern matching).

  1. This was all assuming you've made merge a separate function. You don't need that many Boolean flags to maintain state if you do sequential merging. If you haven't split them up already, then do it now.

  2. Splitting the array into parts can be handles by the splitAt(Int)function of Array, which takes as a parameter the index to split the array at, and returns a tuple containing the left and right parts. So, we could have the following:

     (leftArr, rightArr) = arr splitAt (arr.length / 2)
    

You sure you still don't want pattern matching?

Just to show off pattern matching, the canonical Scala solution (adapted to work on Seqs for Scala 2.10+, is the following:

    def mergeSort[T <: Ordered[T]](xs: Seq[T]): Seq[T] = {
      val n = xs.length / 2
      if (n == 0) xs
      else {
        def merge(xs: Seq[T], ys: Seq[T]): Seq[T] =
            (xs, ys) match {
            case(Nil, ys) => ys
            case(xs, Nil) => xs
            case(x :: xs1, y :: ys1) =>
              if (x < y) x::merge(xs1, ys)
              else y :: merge(xs, ys1)
        }
        val (left, right) = xs splitAt(n)
        merge(mergeSort(left), mergeSort(right))
      }
    }

Enriched with parameterized types (generics for a non-math guy)!

And for a code-golf answer, which doesn't really handle empty lists, see @lambruscoAcido's answer on PPCGSE.

\$\endgroup\$
  • \$\begingroup\$ Thanks for the answer Tamoghna. FYI - I am intentionally using Scala as a Imperative language for personal purposes. I do know all the functional paradigm, but as I said, I am experimentally doing it in "lower-level" way. \$\endgroup\$ – Filipe Miranda Nov 24 '16 at 21:56

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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