Итерационный подход сортировки слиянием в Javascript

Question

Я пытаюсь реализовать сортировку слиянием итеративно, но в javascript. Я тоже пробовал искать в Интернете, но они есть только на C, Python и java. Массив, который дает моя функция, не отсортирован. Я пробовал разные вещи, но не могу понять ошибку. Может кто-нибудь указать, пожалуйста, что я делаю не так?

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

Ошибка в вашем коде заключается в непоследовательном определении того, что midи rightEndозначает.

Из следующего кода мы узнаем, что эти индексы указывают на запись после предыдущего подмассива:

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

Но если посмотреть на задания:

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

... мы видим, что они указывают на последний элемент предыдущего подмассива.

Вы можете исправить это двумя способами, но поскольку способ sliceинтерпретации аргументов является «стандартным», я бы предложил внести исправления в назначения, удалив все это - 1следующим образом:

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

Answer 2

Пранав: Я процитировал ниже алгоритм итеративной сортировки слиянием, предоставленный Майклом Ласло на аналогичный вопрос, заданный ранее: итеративная реализация сортировки слиянием

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