Merge Two Sorted Arrays Without Extra Space in DSA C - Execution Trace

Concept Flow - Merge Two Sorted Arrays Without Extra Space

Start with two sorted arrays

↓

Compare last element of first array with first of second

↓

If first array's last > second array's first

Yes↓

Swap these two elements

↓

Sort both arrays individually

↓

Repeat comparison until no swaps needed

↓

Arrays merged without extra space

We repeatedly compare and swap elements between arrays, then sort them individually until both arrays are sorted together without extra space.

Execution Sample

DSA C

int i = n - 1, j = 0;
while (i >= 0 && j < m) {
  if (arr1[i] > arr2[j]) {
    int temp = arr1[i];
    arr1[i] = arr2[j];
    arr2[j] = temp;
    i--;
    j++;
  } else {
    break;
  }
}
sort(arr1, arr1 + n);
sort(arr2, arr2 + m);

This code merges two sorted arrays by swapping elements and sorting them without extra space.

Execution Table

Step	Operation	i (arr1 index)	j (arr2 index)	Swap?	arr1 State	arr2 State
1	Compare arr1[4]=9 and arr2[0]=2	4	0	Yes	[1, 3, 5, 7, 2]	[9, 9, 10, 12, 15]
2	Compare arr1[3]=7 and arr2[1]=9	3	1	No	[1, 3, 5, 7, 2]	[9, 9, 10, 12, 15]
3	Sort arr1	-	-	No	[1, 2, 3, 5, 7]	[9, 9, 10, 12, 15]
4	Sort arr2	-	-	No	[1, 2, 3, 5, 7]	[9, 9, 10, 12, 15]
Exit	No more swaps needed	-	-	-	[1, 2, 3, 5, 7]	[9, 9, 10, 12, 15]

💡 Stopped when arr1[i] <= arr2[j], no more swaps needed

Variable Tracker

Variable	Start	After Step 1	After Step 2	After Step 3	After Step 4	Final
i	4	3	3	-	-	-
j	0	1	1	-	-	-
arr1	[1, 3, 5, 7, 9]	[1, 3, 5, 7, 2]	[1, 3, 5, 7, 2]	[1, 2, 3, 5, 7]	[1, 2, 3, 5, 7]	[1, 2, 3, 5, 7]
arr2	[2, 9, 10, 12, 15]	[9, 9, 10, 12, 15]	[9, 9, 10, 12, 15]	[9, 9, 10, 12, 15]	[9, 9, 10, 12, 15]	[9, 9, 10, 12, 15]

Key Moments - 3 Insights

Why do we compare arr1[i] with arr2[j] starting from the end of arr1 and start of arr2?

Because arr1 is sorted ascending, its largest elements are at the end, and arr2's smallest are at the start. Comparing these helps identify elements to swap to maintain sorted order without extra space, as shown in execution_table step 1.

Why do we sort both arrays after swapping elements?

Swapping may break the sorted order in both arrays. Sorting them individually restores order, ensuring the merged arrays remain sorted without extra space, as seen in steps 3 and 4.

Why does the loop stop when arr1[i] <= arr2[j]?

Because no further swaps are needed if the largest element in arr1 is less or equal to the smallest in arr2, meaning arrays are correctly partitioned, as shown in step 2 where the loop breaks.

Visual Quiz - 3 Questions

Look at the execution_table at step 1, what elements are swapped?

A arr1[4] and arr2[0]

B arr1[3] and arr2[1]

C arr1[0] and arr2[4]

D arr1[2] and arr2[2]

💡 Hint

Check the 'Swap?' and 'Operation' columns in execution_table step 1

At which step does the loop stop because no swap is needed?

A Step 1

B Step 3

C Step 2

D Step 4

💡 Hint

Look at the 'Swap?' column and 'Exit' note in execution_table

If we did not sort arr1 and arr2 after swapping, what would happen?

A Arrays would remain sorted

B Arrays might become unsorted

C Swapping would not occur

D Loop would never stop

💡 Hint

Refer to key_moments explanation about sorting after swapping

Concept Snapshot

Merge Two Sorted Arrays Without Extra Space:
- Compare last of arr1 and first of arr2
- Swap if arr1's element is bigger
- Sort both arrays after swaps
- Repeat until no swaps needed
- Result: two sorted arrays merged without extra space

Full Transcript

This concept shows how to merge two sorted arrays without using extra space. We start by comparing the last element of the first array with the first element of the second array. If the first array's element is bigger, we swap them. After swapping, we sort both arrays individually to maintain order. We repeat this process until no more swaps are needed, meaning the arrays are merged correctly. This method avoids extra memory by rearranging elements in place.

Practice

1. What is the main goal when merging two sorted arrays without extra space?

easy

A. Combine both arrays into one sorted array without using extra memory

B. Sort each array separately using extra memory

C. Copy elements from one array to another without sorting

D. Create a new array to hold merged elements

Solution

1. Step 1: Understand the problem requirement

   The task is to merge two sorted arrays into a single sorted sequence without using extra space, meaning no additional arrays or large buffers.

2. Step 2: Identify the correct approach

   We must rearrange elements within the given arrays to maintain sorted order without allocating extra memory.

3. Final Answer:

   Combine both arrays into one sorted array without using extra memory -> Option A

4. Quick Check:

   Merge without extra space = Combine in place [OK]

Hint: Merge by swapping elements, no extra array needed [OK]

Common Mistakes:

• Thinking extra array is allowed
• Sorting arrays separately without merging
• Copying elements without sorting

2. Which of the following C code snippets correctly declares two sorted arrays for merging without extra space?

easy

A. int arr1[] = (1, 3, 5); int arr2[] = (2, 4, 6);

B. int arr1 = {1, 3, 5}; int arr2 = {2, 4, 6};

C. int arr1[] = [1, 3, 5]; int arr2[] = [2, 4, 6];

D. int arr1[] = {1, 3, 5}; int arr2[] = {2, 4, 6};

Solution

1. Step 1: Check array declaration syntax in C

   Arrays in C are declared using curly braces {} with type and square brackets [].

2. Step 2: Validate each option

   int arr1[] = {1, 3, 5}; int arr2[] = {2, 4, 6}; uses correct syntax: int arr[] = {elements}; Options A, B, and D use invalid syntax for arrays in C.

3. Final Answer:

   int arr1[] = {1, 3, 5}; int arr2[] = {2, 4, 6}; -> Option D

4. Quick Check:

   C arrays use {} for initialization [OK]

Hint: Use curly braces {} to initialize arrays in C [OK]

Common Mistakes:

• Using parentheses () or square brackets [] for initialization
• Missing data type or brackets
• Assigning arrays without braces

3. Given two sorted arrays:
arr1 = {1, 4, 7, 8, 10}
arr2 = {2, 3, 9}
After merging without extra space, what will be the content of arr1?

medium

A. [1, 2, 3, 4, 8]

B. [1, 2, 3, 4, 7]

C. [1, 2, 3, 7, 8]

D. [1, 3, 4, 7, 8]

Solution

1. Step 1: Understand merging without extra space

   We merge by comparing elements and swapping to keep smallest elements in arr1.

2. Step 2: Merge process

   Initial arr1: [1,4,7,8,10], arr2: [2,3,9]
   Compare 10 (arr1 last) and 2 (arr2 first), swap -> arr1: [1,4,7,8,2], arr2: [10,3,9]
   Sort arr2: [3,9,10]
   Repeat swaps and sorts until arr1 holds smallest 5 elements:
   Final arr1: [1,2,3,4,7]

3. Final Answer:

   [1, 2, 3, 4, 7] -> Option B

4. Quick Check:

   Smallest 5 elements in arr1 after merge = [1,2,3,4,7] [OK]

Hint: Keep smallest elements in first array by swapping [OK]

Common Mistakes:

• Not sorting arr2 after swaps
• Assuming arr1 remains unchanged
• Mixing elements without sorting

4. Identify the error in this code snippet for merging two sorted arrays without extra space:

for (int i = 0; i < n; i++) {
  if (arr1[i] > arr2[0]) {
    int temp = arr1[i];
    arr1[i] = arr2[0];
    arr2[0] = temp;
    sort(arr2, arr2 + m);
  }
}

medium

A. Using sort() without including <algorithm> header

B. Swapping elements incorrectly between arrays

C. Sorting arr2 inside the loop causes inefficiency

D. Loop should run from 0 to m instead of n

Solution

1. Step 1: Analyze the loop and sorting

   The code swaps elements and sorts arr2 inside the loop for every iteration.

2. Step 2: Identify inefficiency

   Sorting arr2 in every iteration is costly and inefficient; better to optimize sorting or use a different approach.

3. Final Answer:

   Sorting arr2 inside the loop causes inefficiency -> Option C

4. Quick Check:

   Sorting inside loop = inefficient [OK]

Hint: Avoid sorting inside loops for better performance [OK]

Common Mistakes:

• Ignoring performance impact of repeated sorting
• Confusing array sizes for loop limits
• Assuming swap logic is incorrect

5. You have two sorted arrays:
arr1 = {1, 5, 9, 10, 15, 20}
arr2 = {2, 3, 8, 13}
Using the gap method to merge without extra space, what is the final state of arr2 after merging?

hard

A. [10, 13, 15, 20]

B. [8, 9, 10, 15]

C. [8, 13, 15, 20]

D. [9, 10, 13, 15]

Solution

1. Step 1: Understand the gap method

   The gap method compares elements at a gap distance and swaps if out of order, reducing gap until 1.

2. Step 2: Apply gap method to arrays

   Initial arr1: [1,5,9,10,15,20], arr2: [2,3,8,13]
   After merging, arr1 holds smallest elements: [1,2,3,5,8,9]
   arr2 holds remaining elements: [10,13,15,20]

3. Step 3: Final arr2 state

   arr2 after merge is [10, 13, 15, 20].

4. Final Answer:

   [10, 13, 15, 20] -> Option A

5. Quick Check:

   Gap method final arr2 = [10, 13, 15, 20] [OK]

Hint: Gap method sorts by comparing distant elements [OK]

Common Mistakes:

• Confusing final positions of elements in arr2
• Assuming arr2 remains unchanged
• Misapplying gap calculation