Approche itérative de Merge Sort en Javascript

Question

J'essaye d'implémenter le tri de fusion de manière itérative mais en javascript. J'ai également essayé de rechercher sur Internet, mais ils n'ont que C, Python et java. Le tableau que ma fonction donne n'est pas trié. J'ai essayé différentes choses mais je n'arrive pas à comprendre l'erreur. Quelqu'un peut-il indiquer s'il vous plaît ce que je fais mal?

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

L'erreur dans votre code est dans une définition incohérente de ce que midet rightEndsignifie.

À partir du code suivant, nous apprenons que ces index pointent vers l'entrée après le sous-tableau précédent:

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

Mais en regardant les affectations:

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

... nous voyons qu'ils pointent vers le dernier élément du sous-tableau précédent.

Vous pouvez corriger cela de deux manières, mais comme la manière d' sliceinterpréter ses arguments est la manière "standard", je suggère de faire la correction dans les affectations, en supprimant toutes celles-ci - 1, comme suit:

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

Answer 2

Pranav: J'ai cité ci-dessous un algorithme de tri de fusion itératif fourni par Michael Laszlo à une question similaire posée auparavant: Implémentation du tri de fusion de manière itérative

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(', '));