why does this merge sort code work in python but not in javascript

Question

Does anyone know why this code isn't working, I tried the same code in python and it worked perfectly.

function merge(l, m, r) {
    let divider = m + 1
    let l_cache = l
    let out_list = []
    for (let i = 0; i < r - l + 1; i++) {
        if (l > m) {
            out_list.push(numbers[divider])
            divider += 1
        } else if (divider > r) {
            out_list.push(numbers[l])
            l += 1
        } else if (numbers[l] < numbers[divider]) {
            out_list.push(numbers[l])
            l += 1
        } else if (numbers[l] >= numbers[divider]) {
            out_list.push(numbers[divider])
            divider += 1
        }
    }
    for (let i = 0; i < out_list.length; i++) {
        numbers[i + l_cache] = out_list[i]
    }
}

function MergeSort(l, r) {
    if (l < r) {
        let m = Math.floor((l + r - 1) / 2)
        MergeSort(l, m)
        MergeSort(m + 1, r)
        merge(l, m, r)
    }
}

var numbers = [ 42, 60, 33, 79, 15, 0, 88, 62, 27, 46 ]
MergeSort(0, numbers.length - 1)

input: [42, 60, 33, 79, 15, 0, 88, 62, 27, 46]

output: [0, 15, 27, 33, 42, 46, 60, 46, 62 ,62]

expected output: [0, 15, 27, 33, 42, 46, 60, 62, 79, 88]

Do you have a link to the original python code ?

px1mp
– px1mp

2021-02-16 19:59:42 +00:00
Commented Feb 16, 2021 at 19:59 — px1mp
– px1mp, Commented Feb 16, 2021 at 19:59

Bergi · Accepted Answer · 2021-02-17 02:52:23Z

1

The problem is that you are mutating l in the loop body, but still using it in your condition in for (let i = 0; i < r-l+1; i++). That way the merge ends too early and out_list doesn't contain everything it should. Fix this by using

for (let i = 0; i < r-l_cache+1; i++) {
//                    ^^^^^^^

In python you probably used a range() which is only evaluated once and keeps its stop value.

Alternatively you might want to not depend on arithmetic to determine the number of iterations beforehand, but use the end condition

while (l <= m || divider <= r) {

answered Feb 17, 2021 at 2:52

Bergi

671k162 gold badges1k silver badges1.5k bronze badges

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

Collectives™ on Stack Overflow

why does this merge sort code work in python but not in 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