Abordagem iterativa de Merge Sort em Javascript

Question

Estou tentando implementar o merge sort iterativamente, mas em javascript. Tentei pesquisar na internet também, mas eles só têm em C, Python e java. O array que minha função está fornecendo não está classificado. Tentei coisas diferentes, mas não consigo descobrir o erro. Alguém pode apontar, por favor, o que estou fazendo de errado?

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

O erro em seu código está em uma definição inconsistente de o que mide o que rightEndsignifica.

Com o código a seguir, aprendemos que esses índices apontam para a entrada após a subarray anterior:

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

Mas ao olhar para as atribuições:

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

... vemos que eles apontam para o elemento final da submatriz anterior.

Você pode corrigir isso de duas maneiras, mas como a forma como sliceinterpreta seus argumentos é a forma "padrão", sugiro fazer a correção nas atribuições, removendo todos eles - 1, da seguinte maneira:

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

Answer 2

Pranav: citei abaixo um algoritmo de classificação por mesclagem iterativa fornecido por Michael Laszlo para uma pergunta semelhante feita anteriormente: Implementando classificação por mesclagem iterativamente

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