Iterativer Ansatz von Merge Sort in Javascript

Question

Ich versuche, Merge Sort iterativ aber in Javascript zu implementieren. Ich habe auch versucht, im Internet zu suchen, aber sie haben nur in C, Python und Java. Das Array, das meine Funktion gibt, ist nicht sortiert. Ich habe verschiedene Dinge ausprobiert, kann den Fehler aber nicht herausfinden. Kann jemand bitte darauf hinweisen, was ich falsch mache?

function mergeSortIterative(arr){
    let sorted=[...arr];//copying the array so that original remains unchanged.
    let n=sorted.length;
    let currSize;
    let leftStart;
    for(currSize=1;currSize<=n-1;currSize=2*currSize){
        for(leftStart=0;leftStart<n-1;leftStart+=2*currSize){
            let mid=Math.min(leftStart+currSize-1,n-1);
            let rightEnd=Math.min(leftStart+2*currSize-1,n-1);
            // let left=sorted.slice(leftStart,mid);
            // let right=sorted.slice(mid,rightEnd);
            // sorted=mergeIterative(sorted,left,right);
            mergeIterative(sorted,leftStart,mid,rightEnd);
        }
    }
    return sorted;
}

function mergeIterative(sorted,leftStart,mid,rightEnd){
    let left=sorted.slice(leftStart,mid);
    let right=sorted.slice(mid,rightEnd);
    let leftIndex=0,rightIndex=0,k=leftStart;
    while(leftIndex<left.length && rightIndex<right.length){
        //picking the lesser one 
        if(left[leftIndex]<=right[rightIndex]){
            sorted[k]=left[leftIndex];
            leftIndex++;
            k++;
        }
        else{
            sorted[k]=right[rightIndex];
            rightIndex++;
            k++;
        }
    }
    while(leftIndex<left.length && k<sorted.length){
        sorted[k]=left[leftIndex];
        leftIndex++;
        k++;
    }
    while(rightIndex<right.length && k<sorted.length){
        sorted[k]=right[rightIndex];
        rightIndex++;
        k++;
    }
}

Answer 1

Der Fehler in Ihrem Code liegt in einer inkonsistenten Definition von was midund was rightEnd.

Aus dem folgenden Code erfahren wir, dass diese Indizes auf den Eintrag nach dem vorhergehenden Subarray verweisen:

let left = sorted.slice(leftStart, mid);
let right = sorted.slice(mid, rightEnd);

Aber wenn man sich die Aufgaben ansieht:

let mid = Math.min(leftStart + currSize - 1, n - 1); 
let rightEnd = Math.min(leftStart + 2 * currSize - 1, n - 1);

... wir sehen, dass sie auf das letzte Element des vorhergehenden Unterarrays zeigen.

Sie können dies auf zwei Arten korrigieren, aber da die Art und Weise, wie slicedie Argumente interpretiert werden, die "Standard" -Methode ist, würde ich vorschlagen, die Korrektur in den Zuweisungen vorzunehmen und alle diese - 1wie folgt zu entfernen :

let mid = Math.min(leftStart + currSize, n); 
let rightEnd = Math.min(leftStart + 2 * currSize, n);

Answer 2

Pranav: Ich habe unten einen iterativen Zusammenführungssortieralgorithmus zitiert, der von Michael Laszlo für eine ähnliche Frage bereitgestellt wurde , die zuvor gestellt wurde: Implementieren der Zusammenführungssortierung iterativ

function mergeSort(arr) {
  var sorted = arr.slice(),
      n = sorted.length,
      buffer = new Array(n);

  for (var size = 1; size < n; size *= 2) {
    for (var leftStart = 0; leftStart < n; leftStart += 2*size) {
      var left = leftStart,
          right = Math.min(left + size, n),
          leftLimit = right,
          rightLimit = Math.min(right + size, n),
          i = left;
      while (left < leftLimit && right < rightLimit) {
        if (sorted[left] <= sorted[right]) {
          buffer[i++] = sorted[left++];
        } else {
          buffer[i++] = sorted[right++];
        }
      }
      while (left < leftLimit) {
        buffer[i++] = sorted[left++];
      }
      while (right < rightLimit) {
        buffer[i++] = sorted[right++];
      }
    }
    var temp = sorted,
        sorted = buffer,
        buffer = temp;
  }

  return sorted;
}

function print(s) {
  document.write(s + '<br />');
}

var data = [1, 4, 10, 2, 9, 3];
print('input: ' + data.join(', '));
print('output: ' + mergeSort(data).join(', '));