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 implementation without sorted() involves pattern matching, take a look here for details (especially @Shadowlands' answer for one without explicit pattern matching).
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.
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.
