Merge sort time complexity check

Hello guys

I was learning about the merge sort so I wrote this function that takes 2 arrays and merges them sorted.

Can someone tell me the time complexity of this function? I thought it would be O(n^2) as I am using shift inside a while loop.
Is that correct or am I missing something here?

    const mergeArr = (arr1, arr2) => {
        let mergedArr = [];
        let loops = arr1.length + arr2.length;
    
        while (loops !== 0) {
            if (arr1[0] <= arr2[0] || !arr2[0]) {
                mergedArr.push(arr1[0]);
                arr1.shift();
            } else if (arr1[0] > arr2[0] || !arr1[0]) {
                mergedArr.push(arr2[0]);
                arr2.shift();
            }
            loops--;
        }
        return mergedArr;
    };

Answer

The worst case time complexity is indeed O(n²) when n represents the total number of values involved — which will be the size of the output.

To make this algorithm run in linear time, you can use array indices. I’ll apply this as a change to your code without changing anything else (as there are several other things that could be rewritten):

    const mergeArr = (arr1, arr2) => {
        let mergedArr = [];
        let loops = arr1.length + arr2.length;
        let i = 0;
        let j = 0;
    
        while (loops !== 0) {
            if (arr1[i] <= arr2[j] || j >= arr2.length) {
                mergedArr.push(arr1[i]);
                i++;
            } else if (arr1[i] > arr2[j] || i >= arr1.length) {
                mergedArr.push(arr2[j]);
                j++;
            }
            loops--;
        }
        return mergedArr;
    };

Again, there are several improvements possible that do not relate to time complexity, like for instance:

• the else part does not need another if, as that condition is going to be true, and you really want to execute either of the two cases. So that second case should be unconditional.
• The loop could exit as soon as one of the two input arrays has been consumed, as then you can append the rest of the other array in one statement (after the loop).