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
Test your understanding
Look at the execution_table at step 1, what elements are swapped?
Aarr1[4] and arr2[0]
Barr1[3] and arr2[1]
Carr1[0] and arr2[4]
Darr1[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?
AStep 1
BStep 3
CStep 2
DStep 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?
AArrays would remain sorted
BArrays might become unsorted
CSwapping would not occur
DLoop 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.
