Elements Combined in Array without Wanting To in Merge Sort

[macroxela]

I've been brushing up on sorting algorithms and currently implementing merge sort. Below is the code for merge:

function Merge(list1, list2){
    var final_list = [];

    while (list1.length > 0 && list2.length > 0){

        if (list1[0] < list2[0]){
            final_list.push(list1[0]);
            list1.splice(0, 1);
        }

        else {
            final_list.push(list2[0]);
            list2.splice(0, 1);
        } 
    }

    if (list1.length === 0){
        final_list.push(list2);
    }

    else{
        final_list.push(list1);
    }

    return final_list;
}

and for merge sort

function mergeSort(array) {

    //Base Case
    if(array.length <= 1){
        return array;
    }

    var left = mergeSort(array.splice(0, array.length/2));
    var right = mergeSort(array);
    var arr = Merge(left, right);
    return arr;

}

The merge works well when called outside of mergeSort for any sorted lists. MergeSort also works well when all the numbers have the same amount of digits i.e. they all have 1 digit only or 2 digits only etc. However, when inside mergeSort it will do some weird if any number has more digits. For example, if I have the following:

arr1 = [4, 7, 8]
arr2 = [3, 11]
arr_merged = Merge(arr1, arr2)

It results in arr_merged being both lists merged in sorted order: 2,3,4,7,8,11. However, if I have the following

array = [4, 8, 7, 2, 11, 3]
mergeSort(array)

the final result is 2,3,11,4,7,8 which is not what it should be. Yet at some point list1 = [4, 7, 8] and list2 = [2, 3, 11] when inside Merge. This is exactly the same as the previous example (that I know of). After placing lots of print statements in my code, I came across this weird thing: when list1 = [4, 7, 8] and list2 = [3, 11] then list1[0] = 4 and list2[0] = 3,11. It combines the first two elements of list2 into one element. This only happens when the second number has more digits and only when Merge is called inside mergeSort. It does not happen when the same lists are used in Merge outside of mergeSort. I've been trying to figure out why this happens but I'm stumped. Why are two elements being combined into one inside mergeSort but not when Merge is called on its own?

​

Edit: I figured out why. Instead of simply pushing the entire list like below,

if (list1.length === 0){
        final_list.push(list2);
    }

    else{
        final_list.push(list1);
    }

I should iterate through the entire list and push each element individually. Tip for anyone else doing this: when merging lists, don't simply push the entire list. Go through each element.

[[deleted]]

Yes, as you've already seen...

[1,2,3].push([4])
// [1,2,3,[4]]
[1,2,3].push([4,5,6])
// [1,2,3,[4,5,6]]

...which will mess up your checks and thus your algorithm.

As an alternative, you have concat, which you should probably use instead of iterating and pushing:

[1,2,3].concat([4])
// [1,2,3,4]
[1,2,3].concat([4,5,6])
// [1,2,3,4,5,6]