CODEWITHSUNDEEP
javascriptsortingmergesort
Lucian Fuchs
Lucian Fuchs

Reputation: 11

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

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]

Upvotes: 1

Views: 42

Answers (1)

Bergi
Bergi

Reputation: 664599

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) {

Upvotes: 1

Related Questions