My merge sort function works in Java but not in JavaScript, what am I missing?

Question

I have implemented merge sort in Java and it seems to be working correctly. I have tried to transfer this code over to JavaScript in order to create a visual representation of the merge sort sorting algorithm and I cannot get this same code to work.

Here is the code for my Java implementation:

'''

public class MergeSort {

    public void merge(int[] arr, int[] tmpArr, int lo, int mid, int hi) {

        for (int k = lo; k <= hi; k++) {  // first we copy over the array to our tmp array
            tmpArr[k] = arr[k];
        }

        int left = lo;         // keeps index of left side of tmp array
        int right = mid + 1;    // keeps index of right side of tmp array

        for (int l = lo; l <= hi; l++) {  // l keeps the index of the sorted array
            if (left > mid) {               // will merge remaining values in right side of array
                arr[l] = tmpArr[right];
                right++;
            } else if (right > hi) {         // will merge remaining values in left side of array
                arr[l] = tmpArr[left];
                left++;
            } else if (tmpArr[left] < tmpArr[right]) {  // checks if value in left array is less than value in right array
                arr[l] = tmpArr[left];
                left++;
            } else {
                arr[l] = tmpArr[right];
                right++;
            }
        }
    }

    public void sort(int[] arr) {
        int[] tmpArr = new int[arr.length];
        sort(arr, tmpArr, 0, arr.length - 1);
    }

    public void sort(int[] arr, int[] tmpArr, int lo, int hi) {
        if (lo >= hi) {
            return;
        }

        int mid = lo + ((hi - lo) / 2);
        sort(arr, tmpArr, lo, mid);
        sort(arr, tmpArr, mid + 1, hi);
        merge(arr, tmpArr, lo, mid, hi);
    }
}

'''

Here is my JavaScript implementation:

'''

function merge(arr, tmpArr, lo, mid, hi) {
    tmpArr = arr.slice(lo, hi + 1); // copy array over to tmp array

    left = lo; // keeps index of left side of tmp array
    right = mid + 1; // keeps index of right side of tmp array

    for (index = lo; index <= hi; index++) { // index keeps the index of the sorted array
        if (left > mid) { // will merge remaining values in right side of array
            arr[index] = tmpArr[right];
            right++;
        } else if (right > hi) { // will merge remaining values in left side of array
            arr[index] = tmpArr[left];
            left++;
        } else if (tmpArr[left] < tmpArr[right]) { // checks if value in left array is less than value in right array
            arr[index] = tmpArr[left];
            left++;
        } else if (tmpArr[right] < tmpArr[left]) {
            arr[index] = tmpArr[right];
            right++;
        }
    }
}

function sort(arr, tmpArr, lo, hi) {
    if (lo >= hi) { // gets rid of edge case where array has 1 element
        return;
    }

    mid = Math.floor(lo + ((hi - lo) / 2));
    sort(arr, tmpArr, lo, mid);
    sort(arr, tmpArr, (mid + 1), hi);
    merge(arr, tmpArr, lo, mid, hi);
}

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

'''

I have spent hours tweaking this code and inserting print statements into my code but I can't seem to see why it would work in Java and not JavaScript. I am much more proficient in Java than JavaScript so I assume maybe I am missing something. Any help would be greatly appreciated, thank you in advance.

It sounds like you need to work on your debugging skills. You say you've spent ours tweaking and adding print statements. If you need to add a print statement after every line and make sure each one does exactly what you expect. This might take hours more, but it is the only way to find where the problem is. — Code-Apprentice
– Code-Apprentice, Commented Jul 8, 2021 at 17:01
You are creating a new instance for tmpArr at the begin of the function merge, and then the external reference will be lose. Like Code-Apprentice suggested, it's better to debug your code, putting a breakpoint on the function using the development tools of the browsers, or put the instruction "debugger;" (without quotes) to define one fixed breakpoint — Manuel Romeiro
– Manuel Romeiro, Commented Jul 8, 2021 at 17:43

T.J. Crowder · Accepted Answer · 2021-07-08 17:02:40Z

2

I can't say it's everything that's wrong, but this jumped out right away:

tmpArr = arr.slice(lo, hi + 1); // copy array over to tmp array

This doesn't do what it says it does. Just as with Java, it reassigns the parameter tmpArr to refer to a new array. That means the one that is passed in is never modified.

If you want to replace tmpArr's contents with the contents you've listed, you need to do it the way you did it in Java (or with built-in methods that end up doing the same thing, such as tmpArr.length = 0; tmpArr.push(...arr.slice(lo, hi + 1));).

answered Jul 8, 2021 at 17:02

T.J. Crowder

1.1m201 gold badges2k silver badges2k bronze badges

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

Comments

Unmitigated · Accepted Answer · 2021-07-08 17:26:46Z

Directly set the value at the indexes in tmpArray. Using slice will not allow accessing with the same indexes as in the original array.

for(let i = lo; i <= hi; i++) tmpArr[i] = arr[i];

Don't use global variables inside the functions. Declare them with let or const instead. This causes your sort function to fail because mid is updated by the recursive call (since it is implicitly global), so merge gets called with the wrong arguments.

function sort(arr, tmpArr, lo, hi) {
    if (lo >= hi) {
        return;
    }

    let mid = lo + Math.floor((hi - lo) / 2);
    sort(arr, tmpArr, lo, mid);
    sort(arr, tmpArr, mid + 1, hi);
    merge(arr, tmpArr, lo, mid, hi);
}

function merge(arr, tmpArr, lo, mid, hi) {

    for (let k = lo; k <= hi; k++) {
        tmpArr[k] = arr[k];
    }

    let left = lo;         // keeps index of left side of tmp array
    let right = mid + 1;    // keeps index of right side of tmp array

    for (let l = lo; l <= hi; l++) {  // l keeps the index of the sorted array
        if (left > mid) {               // will merge remaining values in right side of array
            arr[l] = tmpArr[right];
            right++;
        } else if (right > hi) {         // will merge remaining values in left side of array
            arr[l] = tmpArr[left];
            left++;
        } else if (tmpArr[left] < tmpArr[right]) {  // checks if value in left array is less than value in right array
            arr[l] = tmpArr[left];
            left++;
        } else {
            arr[l] = tmpArr[right];
            right++;
        }
    }
}

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

function sort(arr, tmpArr, lo, hi) {
    if (lo >= hi) {
        return;
    }

    let mid = lo + Math.floor((hi - lo) / 2);
    sort(arr, tmpArr, lo, mid);
    sort(arr, tmpArr, mid + 1, hi);
    merge(arr, tmpArr, lo, mid, hi);
}

let arr = [3, -1, 5, 6, 8, 2, 2, 1];
mergeSort(arr);
console.log(arr);

Collectives™ on Stack Overflow

My merge sort function works in Java but not in JavaScript, what am I missing?

2 Answers 2

Comments

2 Comments

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

2 Answers 2

Comments

2 Comments

Your Answer

Sign up or log in

Post as a guest

Related