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;
    };

CodePudding user response：

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

CodePudding user response：

What is the time complexity of this function? I thought it would be O(n²) as I am using shift inside a while loop.

Yes, that's correct. But this is a good example of a function where it makes sense to express the time complexity in terms of two variables, the size of the first array x and the size of the second array y. Then we can derive the time complexity to be O((x y)²) or O(max(x,y)²), but most accurate would be O(x² y²). Using a single variable n could only mean n=x y or n=max(x,y).