Merge Two Sorted Arrays Without Extra Space in DSA Rust - 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

↓

Swap elements

↓

Sort both arrays individually

↓

Repeat until no swaps needed

↓

Done: Both arrays sorted and merged without extra space

We repeatedly compare and swap elements between arrays to keep them sorted, then sort each array individually until fully merged.

Execution Sample

DSA Rust

let mut arr1 = [1, 5, 9, 10, 15, 20];
let mut arr2 = [2, 3, 8, 13];
// Merge without extra space
for i in (0..arr1.len()).rev() {
    if arr1[i] > arr2[0] {
        std::mem::swap(&mut arr1[i], &mut arr2[0]);
        arr2.sort();
    }
}

This code merges two sorted arrays by swapping and sorting the second array repeatedly.

Execution Table

Step	Operation	Index i	Compare arr1[i] and arr2[0]	Swap?	arr1 State	arr2 State
1	Compare last element arr1[5]=20 with arr2[0]=2	5	20 > 2	Yes	[1, 5, 9, 10, 15, 2]	[20, 3, 8, 13]
2	Sort arr2	-	-	No	[1, 5, 9, 10, 15, 2]	[3, 8, 13, 20]
3	Compare arr1[4]=15 with arr2[0]=3	4	15 > 3	Yes	[1, 5, 9, 10, 3, 2]	[15, 8, 13, 20]
4	Sort arr2	-	-	No	[1, 5, 9, 10, 3, 2]	[8, 13, 15, 20]
5	Compare arr1[3]=10 with arr2[0]=8	3	10 > 8	Yes	[1, 5, 9, 8, 3, 2]	[10, 13, 15, 20]
6	Sort arr2	-	-	No	[1, 5, 9, 8, 3, 2]	[10, 13, 15, 20]
7	Compare arr1[2]=9 with arr2[0]=10	2	9 > 10	No	[1, 5, 9, 8, 3, 2]	[10, 13, 15, 20]
8	No swap needed, merge done	-	-	-	[1, 5, 9, 8, 3, 2]	[10, 13, 15, 20]

💡 At step 7, arr1[2]=9 is not greater than arr2[0]=10, so no swap needed and merging is complete.

Variable Tracker

Variable	Start	After Step 1	After Step 2	After Step 3	After Step 4	After Step 5	After Step 6	After Step 7	Final
arr1	[1,5,9,10,15,20]	[1,5,9,10,15,2]	[1,5,9,10,15,2]	[1,5,9,10,3,2]	[1,5,9,10,3,2]	[1,5,9,8,3,2]	[1,5,9,8,3,2]	[1,5,9,8,3,2]	[1,5,9,8,3,2]
arr2	[2,3,8,13]	[20,3,8,13]	[3,8,13,20]	[15,8,13,20]	[8,13,15,20]	[10,13,15,20]	[10,13,15,20]	[10,13,15,20]	[10,13,15,20]
i	N/A	5	N/A	4	N/A	3	N/A	2	N/A

Key Moments - 3 Insights

Why do we sort arr2 after swapping elements?

Because swapping puts a larger element at arr2[0], sorting arr2 restores its sorted order, ensuring correct comparisons in next steps (see steps 2,4,6 in execution_table).

Why do we compare arr1[i] with arr2[0] and not other elements?

Because arr2 is always sorted, its smallest element is at index 0. Comparing with arr2[0] ensures we only swap when arr1[i] is bigger than the smallest in arr2, maintaining order (see execution_table comparisons).

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

Because no further swaps are needed; both arrays are in correct order and merged without extra space (see step 7 in execution_table where condition fails).

Visual Quiz - 3 Questions

Look at the execution_table at step 3, what is the state of arr1?

A [1, 5, 9, 8, 3, 2]

B [1, 5, 9, 10, 15, 2]

C [1, 5, 9, 10, 3, 2]

D [1, 5, 9, 10, 15, 20]

💡 Hint

Check the 'arr1 State' column at step 3 in execution_table.

At which step does the condition arr1[i] > arr2[0] become false?

A Step 5

B Step 7

C Step 1

D Step 3

💡 Hint

Look at the 'Compare arr1[i] and arr2[0]' column in execution_table.

If we skip sorting arr2 after swapping, what will happen?

A arr2 becomes unsorted, causing wrong comparisons

B arr2 remains sorted, no issue

C arr1 becomes unsorted

D No change in arrays

💡 Hint

Refer to key_moments about why sorting arr2 after swap is necessary.

Concept Snapshot

Merge Two Sorted Arrays Without Extra Space:
- Compare last element of arr1 with first of arr2
- If arr1[i] > arr2[0], swap them
- Sort arr2 to maintain order
- Repeat for all elements in arr1
- Stop when no swaps needed
- Result: two sorted arrays merged without extra space

Full Transcript

This concept merges two sorted arrays without using extra space by repeatedly comparing the last element of the first array with the first element of the second array. If the element in the first array is greater, we swap it with the smaller element in the second array and then sort the second array to keep it sorted. This process repeats until no more swaps are needed, ensuring both arrays are sorted and merged. The execution table shows each step, the arrays' states, and when the process stops. Key moments clarify why sorting the second array after swapping is essential and why comparisons focus on specific elements. The visual quiz tests understanding of array states and conditions during the merge.

Practice

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

1. 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.

2. Step 2: Identify the correct approach

   We must rearrange elements within the given arrays to maintain sorted order combined, without additional memory.

3. Final Answer:

   Combine both arrays into one sorted sequence without using extra memory -> Option B

4. 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);

Solution

1. Step 1: Identify correct Rust mutable array declaration

   In Rust, arrays are declared with let mut for mutability and square brackets for arrays.

2. 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.

3. Final Answer:

   let mut arr1 = [1, 3, 5]; let mut arr2 = [2, 4, 6]; -> Option A

4. 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

1. 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.

2. 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.

3. Final Answer:

   arr1 = [1, 2, 4], arr2 = [5, 6, 7] -> Option D

4. 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

1. Step 1: Analyze the loop and sorting inside it

   The code sorts arr2 inside the loop for every iteration, which is inefficient and unnecessary.

2. 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.

3. Final Answer:

   Sorting arr2 inside the loop is inefficient and incorrect -> Option C

4. 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

1. 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.

2. 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].

3. Final Answer:

   arr1 = [0, 1, 2, 3], arr2 = [5, 6, 7, 8, 9] -> Option A

4. Quick Check:

   First 4 smallest in arr1, rest in arr2 [OK]

Hint: Place smallest elements in arr1 by swapping, then sort arr2 [OK]

Common Mistakes:

• Not handling different array sizes correctly
• Failing to keep both arrays sorted after merge
• Assuming extra space is allowed