We want to combine two sorted lists into one sorted order without using extra space. We do this by comparing and swapping elements between the two lists to keep them sorted.
Analogy: Imagine you have two sorted stacks of books on two tables. Instead of moving all books to a new table, you pick the smallest book from the second table and swap it with a bigger book from the first table, so both tables stay sorted without extra space.
Goal: Merge both arrays so that all elements are sorted across both arrays without using extra space
Step 1: Compare last element of Array1 (20) with first element of Array2 (2), swap because 20 > 2
[1, 5, 9, 10, 15, 2]
[20, 3, 8, 13]
Why: We want smaller elements in Array1 and larger in Array2 to keep arrays sorted
Step 2: Sort Array2 after swap to keep it sorted: swap 20 and 3, then 20 and 8, then 20 and 13
[1, 5, 9, 10, 15, 2]
[3, 8, 13, 20]
Why: Array2 must remain sorted after swapping in a bigger element
Step 3: Compare last element of Array1 (2) with first element of Array2 (3), no swap needed
[1, 5, 9, 10, 15, 2]
[3, 8, 13, 20]
Why: Elements are in correct order, no change needed
Step 4: Sort Array1 to fix the swapped element 2 at the end: swap 2 and 15
[1, 5, 9, 10, 2, 15]
[3, 8, 13, 20]
Why: Array1 must be sorted after swap
Step 5: Continue sorting Array1: swap 2 and 10
[1, 5, 9, 2, 10, 15]
[3, 8, 13, 20]
Why: Fix order in Array1
Step 6: Continue sorting Array1: swap 2 and 9
[1, 5, 2, 9, 10, 15]
[3, 8, 13, 20]
Why: Fix order in Array1
Step 7: Continue sorting Array1: swap 2 and 5
[1, 2, 5, 9, 10, 15]
[3, 8, 13, 20]
Why: Fix order in Array1
Step 8: Final arrays are sorted without extra space
[1, 2, 5, 9, 10, 15]
[3, 8, 13, 20]
Why: Both arrays are sorted and merged logically
Result:
[1, 2, 5, 9, 10, 15]
[3, 8, 13, 20]
Annotated Code
DSA Rust
fn merge_sorted_arrays(arr1: &mut [i32], arr2: &mut [i32]) {
let n = arr1.len();
let m = arr2.len();
for i in0..n {
if arr1[i] > arr2[0] {
let temp = arr1[i];
arr1[i] = arr2[0];
arr2[0] = temp;
// Place arr2[0] to correct position to keep arr2 sorted
let mut first = arr2[0];
let mut k = 1;
while k < m && arr2[k] < first {
arr2[k - 1] = arr2[k];
k += 1;
}
arr2[k - 1] = first;
}
}
// Sort arr1 after swaps
arr1.sort();
}
fn main() {
let mut arr1 = vec![1, 5, 9, 10, 15, 20];
let mut arr2 = vec![2, 3, 8, 13];
merge_sorted_arrays(&mut arr1, &mut arr2);
println!("{:?}", arr1);
println!("{:?}", arr2);
}
for i in 0..n {
iterate over each element in arr1 to compare with arr2
if arr1[i] > arr2[0] {
check if current arr1 element is bigger than smallest arr2 element
let temp = arr1[i]; arr1[i] = arr2[0]; arr2[0] = temp;
swap arr1[i] with arr2[0] to keep smaller elements in arr1
while k < m && arr2[k] < first { arr2[k - 1] = arr2[k]; k += 1; }
shift arr2 elements to insert swapped element in sorted position
arr1.sort();
sort arr1 after all swaps to restore order
OutputSuccess
[1, 2, 5, 9, 10, 15]
[3, 8, 13, 20]
Complexity Analysis
Time: O(n*m) because for each element in arr1 we may shift elements in arr2 to keep it sorted
Space: O(1) because no extra arrays or lists are used, only swaps and shifts inside given arrays
vs Alternative: Naive approach uses extra space to merge both arrays and then sort, costing O(n+m) space; this method saves space but may be slower
Edge Cases
One or both arrays empty
No swaps needed, arrays remain as is
DSA Rust
for i in0..n { if arr1[i] > arr2[0] { ... } }
All elements in arr1 smaller than arr2
No swaps happen, arrays remain sorted
DSA Rust
if arr1[i] > arr2[0] { ... }
All elements in arr1 larger than arr2
Multiple swaps and shifts happen to reorder arrays
DSA Rust
while k < m && arr2[k] < first { ... }
When to Use This Pattern
When asked to merge two sorted arrays without extra space, use this swapping and shifting pattern to keep arrays sorted in place.
Common Mistakes
Mistake: Trying to merge by just appending and sorting, which uses extra space Fix: Use element-wise comparison and swapping to avoid extra space
Mistake: Not shifting elements in second array after swap, breaking its sorted order Fix: Shift elements in second array to insert swapped element correctly
Summary
Merges two sorted arrays into sorted order without using extra space by swapping and shifting elements.
Use when you must merge sorted arrays but cannot allocate extra memory.
The key is to swap bigger elements from first array with smaller from second, then fix order by shifting.
Practice
(1/5)
1. What is the main goal when merging two sorted arrays without extra space?
easy
A. Sort each array separately using extra space
B. Combine both arrays into one sorted sequence without using extra memory
C. Copy elements from one array to another without sorting
D. Create a new array to hold merged elements
Solution
Step 1: Understand the problem requirement
The problem asks to merge two sorted arrays into a sorted sequence without using extra space, meaning no new arrays can be created.
Step 2: Identify the correct approach
We must rearrange elements within the given arrays to maintain sorted order combined, without additional memory.
Final Answer:
Combine both arrays into one sorted sequence without using extra memory -> Option B
Quick Check:
Merge without extra space = Combine in place [OK]
Hint: Merge by swapping elements, no new arrays needed [OK]
Common Mistakes:
Trying to create a new array for merged result
Sorting arrays separately without merging
Ignoring the no extra space constraint
2. Which Rust syntax correctly declares two mutable sorted arrays for merging without extra space?
easy
A. let mut arr1 = [1, 3, 5]; let mut arr2 = [2, 4, 6];
B. let arr1 = [1, 3, 5]; let arr2 = [2, 4, 6];
C. mut arr1 = [1, 3, 5]; mut arr2 = [2, 4, 6];
D. let mut arr1 = (1, 3, 5); let mut arr2 = (2, 4, 6);
In Rust, arrays are declared with let mut for mutability and square brackets for arrays.
Step 2: Check each option
let mut arr1 = [1, 3, 5]; let mut arr2 = [2, 4, 6]; uses let mut with arrays correctly. let arr1 = [1, 3, 5]; let arr2 = [2, 4, 6]; misses mut keyword. mut arr1 = [1, 3, 5]; mut arr2 = [2, 4, 6]; misses let keyword. let mut arr1 = (1, 3, 5); let mut arr2 = (2, 4, 6); uses tuples, not arrays.
Final Answer:
let mut arr1 = [1, 3, 5]; let mut arr2 = [2, 4, 6]; -> Option A
Quick Check:
Mutable arrays use let mut and [] [OK]
Hint: Use let mut and square brackets for mutable arrays [OK]
Common Mistakes:
Forgetting mut keyword for mutable arrays
Using tuples instead of arrays
Missing let keyword
3. What will be the content of arrays after merging arr1 = [1, 4, 7] and arr2 = [2, 5, 6] without extra space using the gap method?
medium
A. ]7 ,6 ,5[ = 2rra ,]4 ,2 ,1[ = 1rra
B. arr1 = [1, 4, 5], arr2 = [2, 6, 7]
C. rr1 = [1, 2, 4], arr2 = [5, 6, 7]
D. arr1 = [1, 2, 4], arr2 = [5, 6, 7]
Solution
Step 1: Apply gap method to merge arrays
Start with gap = ceil((3+3)/2) = 3. Compare and swap elements at gap distance across arrays until gap reduces to 0.
Step 2: Final arrays after merging
After applying gap method, arr1 becomes [1, 2, 4] and arr2 becomes [5, 6, 7], maintaining sorted order without extra space.
Final Answer:
arr1 = [1, 2, 4], arr2 = [5, 6, 7] -> Option D
Quick Check:
Gap method merges arrays in place [OK]
Hint: Use gap method to compare and swap elements at decreasing gaps [OK]
Common Mistakes:
Not reducing gap correctly
Swapping elements incorrectly across arrays
Confusing array indices during merge
4. Identify the error in this Rust code snippet for merging two sorted arrays without extra space:
let mut arr1 = [1, 5, 9];
let mut arr2 = [2, 6, 8];
for i in 0..arr1.len() {
if arr1[i] > arr2[0] {
let temp = arr1[i];
arr1[i] = arr2[0];
arr2[0] = temp;
}
arr2.sort();
}
medium
A. Using let temp causes ownership error in Rust
B. Swapping elements between arr1 and arr2 is not allowed
C. Sorting arr2 inside the loop is inefficient and incorrect
D. The loop range should be arr2.len() instead of arr1.len()
Solution
Step 1: Analyze the loop and sorting inside it
The code sorts arr2 inside the loop for every iteration, which is inefficient and unnecessary.
Step 2: Correct approach for sorting arr2
Sorting arr2 should be done once after all swaps, not inside the loop, to improve performance and correctness.
Final Answer:
Sorting arr2 inside the loop is inefficient and incorrect -> Option C
Quick Check:
Sort arr2 once after loop [OK]
Hint: Sort arr2 once after loop, not inside it [OK]
Common Mistakes:
Sorting arr2 repeatedly inside loop
Confusing loop ranges
Misunderstanding Rust ownership with temp variable
5. Given two sorted arrays arr1 = [1, 3, 5, 7] and arr2 = [0, 2, 6, 8, 9], how can you merge them without extra space so that after merging, arr1 contains the first 4 smallest elements and arr2 contains the remaining elements sorted? Choose the correct final arrays.
hard
A. arr1 = [0, 1, 2, 3], arr2 = [5, 6, 7, 8, 9]
B. arr1 = [1, 2, 3, 5], arr2 = [0, 6, 7, 8, 9]
C. arr1 = [0, 1, 3, 5], arr2 = [2, 6, 7, 8, 9]
D. arr1 = [0, 1, 3, 6], arr2 = [2, 5, 7, 8, 9]
Solution
Step 1: Understand merging without extra space for unequal sizes
We must rearrange elements so arr1 holds smallest 4 elements and arr2 holds the rest, both sorted.
Step 2: Apply gap method or swapping approach
By comparing and swapping elements between arrays and sorting arr2, final arrays become arr1 = [0, 1, 2, 3] and arr2 = [5, 6, 7, 8, 9].
