Search code examples
javascriptarraysalgorithmmergesort

Merge sort algorithm works in golang but not javascript


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]);

Solution

  • 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];
        }