Why does using >= increase merge sort time complexity

Question

I recently solved the Merge Sorted Array question on leetcode
Here is the part of the code I am having doubts on :

while (curr >= 0 && p1 >= 0 && p2 >= 0) {
    // more TC if we use the condition >= , not sure of the reason 
    if (nums1[p1] > nums2[p2]) {
        nums1[curr] = nums1[p1];
        nums1[p1] = 0;   // replacing 0 and greater number in nums1
        p1--;
    } else {
        nums1[curr] = nums2[p2];
        p2--;
    }
    curr--;
}

I noticed that when I use >= in the while condition (instead of >), the time complexity seems to increase or the solution behaves slower. Why ?

Which one of the three (four) >= are you talking about? Please update your answer. — JayC667
– JayC667, Commented 22 hours ago
Naturally if you use >= instead of > you'd have 1 extra case in all scenarios to compute for: the == case. So you've already got inherently more work out the gate, computational performance aside. — Rogue
– Rogue, Commented 22 hours ago
Time or Time Complexity? It does not increase Time Complexity, which is a rough estimate method of comparing best/worst/average cases. It's still O(whatever). It might increase time to run the algorithm, depending on the exact data fed, but not the complexity. — Gabe Sechan
– Gabe Sechan, Commented 22 hours ago
@GabeSechan - " ... Time Complexity, which is a rough estimate method of comparing best/worst/average cases ..." is inaccurate. 1) The 'case' (best/average/worst) that you are measuring is orthogonal to the method of measurement (complexity). 2) Complexity is actually a characterization of how the algorithm scales rather than a "rough estimate". For a start, complexity doesn't give you a meaningful number. — Stephen C
– Stephen C, Commented 5 hours ago

Gabe Sechan · Accepted Answer · 2025-11-21 17:47:28Z

0

Assuming you mean the inner > with >=- there can be several answers. One obvious one is that the if branch does more work, so putting more in there is slower. I'm not sure why you have nums1[p1] = 0; in there, it doesn't seem necessary. Beyond that you can get into things on the hardware and interpreter level- the JIT cache guessing wrong on the branch prediction (or the hardware itself). Locality issues in the cache maybe. But its mostly going to be the extra instruction most likely.

If you mean one or more of the > in the while loop- yeah, that adds more cases where the while loop runs. More runs=more time.

Although as I stated in a comment- this is time to run, not time complexity. None of these would change time complexity.

answered 21 hours ago

Gabe Sechan

94.7k9 gold badges92 silver badges135 bronze badges

Sign up to request clarification or add additional context in comments.

Comments

rcgldr · Accepted Answer · 2025-11-22 08:03:46Z

There seemed to be potential issues with the question's code, so I used a modified version of old merge sort code that passed the leetcode tests (apparently 59 tests are run). My example code checks m and n before attempting a merge. The merge loop checks for end of array after moving an integer, rather than before.

In the case where all elements are equal, using > will not move any elements of nums1 and only move all of nums2 to the end of nums1 for time complexity O(n), while using >= will move all of nums1 to the end of nums1 and all of nums2 to the beginning of nums1, for time complexity O(m+n).

Using >= instead of > will break stability (not an issue if sorting native integers).

    public static void merge(int nums1[], int m, int nums2[], int n)
    {
        int curr;
        if(m < 0)
            return;
        if(n <= 0)
            return;
        if(m == 0){
            do
                nums1[m] = nums2[m++];
            while(m < n);
            return;
        }
        m--;
        n--;
        curr = m+n+1;
        while(true){
            if(nums1[m] > nums2[n]){
                nums1[curr--] = nums1[m--];
                if(m < 0){
                    do
                        nums1[curr--] = nums2[n--];
                    while(n >= 0);
                    return;
                }
            }else{
                nums1[curr--] = nums2[n--];
                if(n < 0){
                    return;
                }
            }
        }
    }

Collectives™ on Stack Overflow

Why does using >= increase merge sort time complexity

2 Answers 2

Comments

Comments

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

2 Answers 2

Comments

Comments

Your Answer

Sign up or log in

Post as a guest

Related