Merge sort in one Single Function in Scala

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?

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).

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

Suggestions

-
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.

-
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.

-
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

-
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.

-
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 implemen

StackExchange Code Review Q#148012, answer score: 5