Phương pháp lặp lại của Merge Sort trong Javascript

Question

Tôi đang cố gắng triển khai sắp xếp hợp nhất lặp đi lặp lại nhưng bằng javascript. Tôi cũng đã thử tìm kiếm trên internet nhưng chúng chỉ có bằng C, Python và java. Mảng mà hàm của tôi đang đưa ra không được sắp xếp. Tôi đã thử nhiều cách khác nhau nhưng không thể tìm ra lỗi. Ai đó có thể chỉ ra những gì tôi đang làm sai?

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ỗi trong mã của bạn nằm ở định nghĩa không nhất quán về điều gì midvà rightEndý nghĩa.

Từ đoạn mã sau, chúng ta biết rằng các chỉ mục đó trỏ đến mục nhập sau mảng con trước:

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

Nhưng khi xem các bài tập:

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

... chúng ta thấy rằng chúng trỏ đến phần tử cuối cùng của mảng con trước đó.

Bạn có thể sửa lỗi này theo hai cách, nhưng vì cách slicediễn giải các đối số của nó là cách "tiêu chuẩn", tôi khuyên bạn nên sửa lỗi trong bài tập, loại bỏ tất cả những cách đó - 1, như sau:

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

Answer 2

Pranav: Tôi đã trích dẫn bên dưới một thuật toán sắp xếp hợp nhất lặp đi lặp lại do Michael Laszlo cung cấp cho một câu hỏi tương tự được hỏi trước đây: Triển khai sắp xếp hợp nhất lặp đi lặp lại

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