Merge sort algorithm works in golang but not javascript

Question

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

trincot · Accepted Answer · 2022-09-24 20:49:44Z

1

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

answered Sep 24, 2022 at 20:49

trincot

357k38 gold badges282 silver badges338 bronze badges

Sign up to request clarification or add additional context in comments.

Collectives™ on Stack Overflow

Merge sort algorithm works in golang but not javascript

1 Answer 1

Comments

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

1 Answer 1

Comments

Your Answer

Sign up or log in

Post as a guest

Related