Zusammenführen für Mergesort in Scala

Question

Ich migriere von Java zu Scala und ich versuche, mit der Prozedur Merge für Mergesort-Algorithmus zu kommen. Meine Lösung:

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

scheint, zu arbeiten, aber es scheint mir, dass es in ganz „Imperativ“ Stil geschrieben (trotz i Rekursion und keine änderbaren Variablen verwendet habe mit Ausnahme der Felder, für die die Nebenwirkung ist gewünscht). Ich möchte etwas wie das:

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

Aber ich kann nicht mit der richtigen Lösung dieser Art kommen. Kannst du mir bitte helfen? diese

Answer 1

Bedenken Sie:

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 
    }