I have a merge sort implementation in Javascript and in golang. It works properly in golang, however, in javascript it seems to always be off by 1. I've havent found any noticeable errors. I would appreciate any insight on to why its failing

I have tried:

• chaning the for iteration to start at leftStart
• changing the middle element from Math.floor to Math.ceil and Math.round
• merging from start to middle-1 and middle to end

function mergeSort(arr) {
  merge(arr, 0, arr.length - 1, []);
}

function merge(arr, start, end, temp) {
  if (start >= end) {
    return;
  }
  const middle = Math.floor((start   end) / 2);
  merge(arr, start, middle, temp);
  merge(arr, middle   1, end, temp);
  mergeHalves(arr, start, end, temp);
}

function mergeHalves(arr, leftStart, rightEnd, temp) {
  const leftEnd = Math.floor((leftStart   rightEnd) / 2);
  const rightStart = leftEnd   1;
  const size = rightEnd - leftStart   1;

  let left = leftStart;
  let right = rightStart;
  let index = left;

  while (left <= leftEnd && right <= rightEnd) {
    if (arr[left] <= arr[right]) {
      temp[index] = arr[left];
      left  ;
    } else {
      temp[index] = arr[right];
      right  ;
    }
    index  ;
  }

  while (left <= leftEnd) {
    temp[index] = arr[left];
    index  ;
    left  ;
  }

  while (right <= rightEnd) {
    temp[index] = arr[right];
    index  ;
    right  ;
  }

  for (let i = 0; i < size; i  ) {
    arr[i] = temp[i];
  }
}

Test case:

    const arr = [2, 1, 3, 5, 6, 2, 7];
    mergeSort(arr);
    //coming back as [1, 2, 3, 5, 6, 2, 7]
    expect(arr).toEqual([1, 2, 2, 3, 5, 6, 7]);

CodePudding user response：

The problem is in this loop:

for (let i = 0; i < size; i  ) {
    arr[i] = temp[i];
}

This is wrong in two ways:

• This assigns values to elements in arr[0..size-1], but that is in general not the range that is merged here. It should target arr[leftStart..rightEnd].

• temp did not collect its values starting at index 0 either. However, that would have been more logical to do, so the fix should be made to how index is initialised earlier in that function.

Here are the corrected lines:

    let index = 0; // not leftStart!
    /* 
        ... the rest of your code ... 
        and finally:
    */
    for (let i = 0; i < size; i  ) {
        arr[leftStart   i] = temp[i];
    }