在 Scala 中合并以进行归并排序

Question

我正在从 Java 迁移到 Scala，我正在尝试为合并排序算法提出合并过程。我的解决方案：

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

似乎可以，但在我看来，它的写法相当 "imperative" 风格（尽管我使用了递归并且除了数组之外没有可变变量，副作用是针对数组的）。我想要这样的东西：

/*
 * 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(<???>)

但是我想不出这种合适的解决方案。你能帮帮我吗？

Answer 1

考虑一下：

  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
  }

在 Scala 中合并以进行归并排序

Merge for mergesort in scala

scala

merge

functional-programming

mergesort