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

by

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]

33 thoughts on “why does this merge sort code work in python but not in javascript”

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

Leave a Comment