Merge for mergesort in scala

Question

I'm migrating from Java to Scala and I am trying to come up with the procedure merge for mergesort algorithm. My solution:

  def merge(src: Array[Int], dst: Array[Int], from: Int,
            mid: Int, until: Int): Unit = {

        /*
         * Iteration of merge:
         * i - index of src[from, mid)
         * j - index of src[mid, until)
         * k - index of dst[from, until)
         */
        @tailrec
        def loop(i: Int, j: Int, k: Int): Unit = {
            if (k >= until) {
                // end of recursive calls
            } else if (i >= mid) {
                dst(k) = src(j)
                loop(i, j + 1, k + 1)
            } else if (j >= until) {
                dst(k) = src(j)
                loop(i + 1, j, k + 1)
            } else if (src(i) <= src(j)) {
                dst(k) = src(i);
                loop(i + 1, j, k + 1)
            } else {
                dst(k) = src(j)
                loop(i, j + 1, k + 1)
            }
        }
        loop(from, mid, from)
  }

seems to work, but it seems to me that it is written in quite "imperative" style (despite i have used recursion and no mutable variables except for the arrays, for which the side effect is intended). I want something like this:

/*
 * this code is not working and at all does the wrong things
 */
for (i <- (from until mid); j <- (mid until until); 
    k <- (from until until) if <???>) yield dst(k) = src(<???>)

But i cant come up with the proper solution of such kind. Can you please help me?

Answer 1

Consider this:

  val left = src.slice(from, mid).buffered
  val right = src.slice(mid, until).buffered

  (from until until) foreach { k => 
    dst(k) = if(!left.hasNext) right.next 
      else if(!right.hasNext || left.head < right.head) left.next
      else right.next
  }