Pendekatan berulang dari Merge Sort di Javascript

Question

Saya mencoba menerapkan merge sort iteratives tetapi dalam javascript. Saya mencoba mencari di internet juga tetapi mereka hanya ada di C, Python, dan java. Array yang diberikan oleh fungsi saya tidak diurutkan. Saya mencoba berbagai hal tetapi tidak dapat menemukan kesalahannya. Bisakah seseorang menunjukkan apa yang saya lakukan salah?

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

Kesalahan dalam kode Anda adalah dalam definisi yang tidak konsisten tentang apa middan rightEndmaksudnya.

Dari kode berikut, kita mengetahui bahwa indeks tersebut mengarah ke entri setelah subarray sebelumnya:

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

Tetapi saat melihat tugas:

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

... kita melihat bahwa mereka menunjuk ke elemen terakhir dari sub larik sebelumnya.

Anda dapat memperbaiki ini dengan dua cara, tetapi karena cara slicemenafsirkan argumennya adalah cara "standar", saya sarankan untuk membuat koreksi dalam tugas, menghapus semua itu - 1, sebagai berikut:

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

Answer 2

Pranav: Saya telah mengutip di bawah ini algoritme pengurutan gabungan berulang yang disediakan oleh Michael Laszlo untuk pertanyaan serupa yang ditanyakan sebelumnya: Menerapkan pengurutan gabungan secara berulang

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