Merge Two Sorted Arrays Without Extra Space in DSA C - Time & Space Complexity

Time Complexity: Merge Two Sorted Arrays Without Extra Space

O((n + m) log n + m)

Understanding Time Complexity

We want to know how the time needed to merge two sorted arrays without extra space changes as the arrays get bigger.

How does the number of steps grow when the input size increases?

Scenario Under Consideration

Analyze the time complexity of the following code snippet.

void merge(int arr1[], int arr2[], int n, int m) {
    int i = 0, j = 0, k = n - 1;
    while (i <= k && j < m) {
        if (arr1[i] < arr2[j]) {
            i++;
        } else {
            int temp = arr2[j];
            arr2[j] = arr1[k];
            arr1[k] = temp;
            j++;
            k--;
        }
    }
    // Sort both arrays after swapping
    qsort(arr1, n, sizeof(int), compare);
    qsort(arr2, m, sizeof(int), compare);
}

This code merges two sorted arrays by swapping elements to avoid extra space, then sorts both arrays again.

Identify Repeating Operations

Identify the loops, recursion, array traversals that repeat.

• Primary operation: The while loop that compares and swaps elements between the two arrays.
• How many times: Up to n + m times, since i moves forward and k moves backward in arr1, and j moves forward in arr2.
• Secondary operations: Sorting both arrays again using qsort, which internally uses a sorting algorithm like quicksort.

How Execution Grows With Input

As the arrays get bigger, the number of comparisons and swaps in the while loop grows roughly with the total size of both arrays.

Input Size (n + m)	Approx. Operations
10	About 10 to 20 operations in the loop, plus sorting small arrays.
100	About 100 to 200 operations in the loop, plus sorting arrays of size 100.
1000	About 1000 to 2000 operations in the loop, plus sorting arrays of size 1000.

Pattern observation: The loop grows linearly with input size, but sorting adds a factor that grows faster than linear.

Final Time Complexity

Time Complexity: O((n + m) log n + m)

This means the time needed grows a bit faster than the total size of the arrays because of the sorting step after swapping.

Common Mistake

[X] Wrong: "The merging without extra space is just a simple linear pass, so it must be O(n + m)."

[OK] Correct: After swapping, the arrays are not fully sorted, so sorting both arrays again takes extra time, which dominates the total time.

Interview Connect

Understanding this helps you explain how to handle merging without extra space and why sorting after swapping affects performance. It shows you can analyze combined steps clearly.

Self-Check

"What if we used a gap method (Shell sort style) to merge without sorting at the end? How would the time complexity change?"