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 element > second array element

↓

Swap elements

↓

Sort both arrays individually

↓

Arrays merged without extra space

We compare elements from the ends of the two arrays, swap if needed, then sort both arrays to merge them without extra space.

Execution Sample

DSA C++

arr1 = [1, 5, 9, 10, 15, 20]
arr2 = [2, 3, 8, 13]
// Merge without extra space
for i from end of arr1 to start:
  if arr1[i] > arr2[0]: swap arr1[i] and arr2[0]; sort arr2
sort arr1

This code merges two sorted arrays by swapping elements and sorting the second array repeatedly, then sorting the first array at the end.

Execution Table

Step	Operation	arr1 State	arr2 State	Pointer Positions	Action Detail
1	Start	[1, 5, 9, 10, 15, 20]	[2, 3, 8, 13]	i=5, j=0	Compare arr1[5]=20 and arr2[0]=2
2	Compare	[1, 5, 9, 10, 15, 20]	[2, 3, 8, 13]	i=5, j=0	20 > 2, swap arr1[5] and arr2[0]
3	Swap	[1, 5, 9, 10, 15, 2]	[20, 3, 8, 13]	i=5, j=0	Swap done
4	Sort arr2	[1, 5, 9, 10, 15, 2]	[3, 8, 13, 20]	i=5, j=0	Sort arr2 after swap
5	Decrement i	[1, 5, 9, 10, 15, 2]	[3, 8, 13, 20]	i=4, j=0	Move to next element in arr1
6	Compare	[1, 5, 9, 10, 15, 2]	[3, 8, 13, 20]	i=4, j=0	15 > 3, swap arr1[4] and arr2[0]
7	Swap	[1, 5, 9, 10, 3, 2]	[15, 8, 13, 20]	i=4, j=0	Swap done
8	Sort arr2	[1, 5, 9, 10, 3, 2]	[8, 13, 15, 20]	i=4, j=0	Sort arr2 after swap
9	Decrement i	[1, 5, 9, 10, 3, 2]	[8, 13, 15, 20]	i=3, j=0	Move to next element in arr1
10	Compare	[1, 5, 9, 10, 3, 2]	[8, 13, 15, 20]	i=3, j=0	10 > 8, swap arr1[3] and arr2[0]
11	Swap	[1, 5, 9, 8, 3, 2]	[10, 13, 15, 20]	i=3, j=0	Swap done
12	Sort arr2	[1, 5, 9, 8, 3, 2]	[10, 13, 15, 20]	i=3, j=0	arr2 already sorted
13	Decrement i	[1, 5, 9, 8, 3, 2]	[10, 13, 15, 20]	i=2, j=0	Move to next element in arr1
14	Compare	[1, 5, 9, 8, 3, 2]	[10, 13, 15, 20]	i=2, j=0	9 > 10? No
15	No Swap	[1, 5, 9, 8, 3, 2]	[10, 13, 15, 20]	i=2, j=0	No swap, move on
16	Decrement i	[1, 5, 9, 8, 3, 2]	[10, 13, 15, 20]	i=1, j=0	Move to next element in arr1
17	Compare	[1, 5, 9, 8, 3, 2]	[10, 13, 15, 20]	i=1, j=0	5 > 10? No
18	No Swap	[1, 5, 9, 8, 3, 2]	[10, 13, 15, 20]	i=1, j=0	No swap, move on
19	Decrement i	[1, 5, 9, 8, 3, 2]	[10, 13, 15, 20]	i=0, j=0	Move to next element in arr1
20	Compare	[1, 5, 9, 8, 3, 2]	[10, 13, 15, 20]	i=0, j=0	1 > 10? No
21	No Swap	[1, 5, 9, 8, 3, 2]	[10, 13, 15, 20]	i=0, j=0	No swap, end loop
22	Sort arr1	[1, 2, 3, 5, 8, 9]	[10, 13, 15, 20]	i=0, j=0	Sort arr1 after all swaps
23	End	[1, 2, 3, 5, 8, 9]	[10, 13, 15, 20]	i=-1, j=0	Merging complete

💡 i reaches -1, loop ends; arrays are merged without extra space

Variable Tracker

Variable	Start	After Step 3	After Step 7	After Step 11	After Step 14	After Step 21	After Step 22	Final
i	5	5	4	3	2	0	0	-1
arr1	[1,5,9,10,15,20]	[1,5,9,10,15,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,2,3,5,8,9]	[1,2,3,5,8,9]
arr2	[2,3,8,13]	[20,3,8,13]	[15,8,13,20]	[10,13,15,20]	[10,13,15,20]	[10,13,15,20]	[10,13,15,20]	[10,13,15,20]

Key Moments - 3 Insights

Why do we sort arr2 after each swap?

Because swapping arr1[i] with arr2[0] can break arr2's sorted order, sorting arr2 restores it. See steps 4, 8, and 12 in execution_table.

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

Because arr2 is always sorted, the smallest element is at arr2[0]. If arr1[i] is bigger, swapping helps move larger elements to arr2. See steps 2, 6, 10.

Why do we sort arr1 only after the loop ends?

Because arr1 remains mostly sorted except for swapped elements at the end. Sorting once at the end is efficient. See step 22.

Visual Quiz - 3 Questions

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

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

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

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

D [1, 5, 9, 8, 15, 2]

💡 Hint

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

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

A Step 10

B Step 14

C Step 18

D Step 21

💡 Hint

Look at the 'Operation' and 'Action Detail' columns around step 14 in execution_table.

If we skip sorting arr2 after swaps, what would happen to the merging process?

A arr2 remains sorted, no effect

B arr2 becomes unsorted, causing incorrect merges

C arr1 becomes unsorted only

D No swaps would occur

💡 Hint

Refer to key_moments explanation about sorting arr2 after swaps.

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 after each swap to maintain order
- Repeat for all elements in arr1
- Finally, sort arr1
- Result: merged arrays without extra space

Full Transcript

This visualization shows how to merge two sorted arrays without extra space by comparing elements from the end of the first array and the start of the second. When the element in the first array is bigger, it is swapped with the smallest element in the second array. After each swap, the second array is sorted to keep it ordered. This process repeats for all elements in the first array. At the end, the first array is sorted once to complete the merge. The execution table tracks each step, showing the arrays' states and pointer positions. Key moments clarify why sorting arr2 after swaps is necessary and why arr1 is sorted only once at the end. The 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. Copy elements from one array to another without sorting

B. Sort each array separately using extra space

C. Create a new array to hold merged elements

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

Solution

1. Step 1: Understand the problem requirement

   The problem asks 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 combined, without allocating new memory.

3. Final Answer:

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

4. Quick Check:

   Merge without extra space = Combine in-place [OK]

Hint: Think in-place rearrangement, no new arrays needed [OK]

Common Mistakes:

• Assuming extra space is allowed
• Trying to merge by creating a new array
• Sorting arrays separately without merging

2. Which of the following C++ code snippets correctly swaps two elements without using extra space?

easy

A. a = a + b; b = a - b; a = a - b;

B. temp = a; a = b; b = temp;

C. a = b; b = a;

D. a = a * b; b = a / b; a = a / b;

Solution

1. Step 1: Analyze swapping without extra variable

   a = a + b; b = a - b; a = a - b; uses arithmetic operations to swap values without a temporary variable.

2. Step 2: Check correctness of each option

   temp = a; a = b; b = temp; uses a temporary variable, so it uses extra space. a = b; b = a; assigns a to b and then b to a, which loses original value. a = a * b; b = a / b; a = a / b; uses multiplication/division which can cause overflow or errors if b is zero.

3. Final Answer:

   a = a + b; b = a - b; a = a - b; -> Option A

4. Quick Check:

   Swap without temp = arithmetic trick [OK]

Hint: Use arithmetic swap to avoid extra variable [OK]

Common Mistakes:

• Using a temporary variable (extra space)
• Overwriting values without saving
• Using multiplication/division causing errors

3. What will be the content of arrays arr1 and arr2 after merging without extra space using the gap method?

arr1 = {1, 5, 9, 10}
arr2 = {2, 3, 8, 13}

medium

A. arr1 = {1, 2, 3, 5}, arr2 = {8, 9, 10, 13}

B. arr1 = {1, 3, 5, 8}, arr2 = {2, 9, 10, 13}

C. arr1 = {1, 2, 5, 8}, arr2 = {3, 9, 10, 13}

D. arr1 = {1, 2, 3, 8}, arr2 = {5, 9, 10, 13}

Solution

1. Step 1: Apply gap method to merge arrays

   Start with gap = ceil((4+4)/2) = 4. Compare elements at gap distance and swap if needed, then reduce gap until 0.

2. Step 2: Final sorted arrays after gap method

   After applying the method, arr1 becomes {1, 2, 3, 5} and arr2 becomes {8, 9, 10, 13}.

3. Final Answer:

   arr1 = {1, 2, 3, 5}, arr2 = {8, 9, 10, 13} -> Option A

4. Quick Check:

   Gap method merges arrays in-place correctly [OK]

Hint: Use gap method: reduce gap, swap if needed [OK]

Common Mistakes:

• Not reducing gap properly
• Swapping wrong elements
• Confusing array indices across two arrays

4. Identify the error in the following code snippet that attempts to merge two sorted arrays without extra space:

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

medium

A. Swapping elements without checking bounds causes runtime error

B. Loop should run till m instead of n

C. Sorting arr2 inside the loop causes high time complexity

D. No error, code is optimal

Solution

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

   The code sorts arr2 inside the loop for every swap, which is inefficient and increases time complexity to O(n*m*log m).

2. Step 2: Identify the performance issue

   Sorting arr2 repeatedly is costly; better methods avoid sorting inside the loop.

3. Final Answer:

   Sorting arr2 inside the loop causes high time complexity -> Option C

4. Quick Check:

   Sorting inside loop = inefficient [OK]

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

Common Mistakes:

• Ignoring time complexity impact
• Assuming swap causes runtime error
• Confusing loop bounds

5. Given two sorted arrays arr1 = {10, 12, 15, 18} and arr2 = {2, 5, 20, 25}, how can you merge them without extra space so that after merging, arr1 contains the first four smallest elements and arr2 contains the remaining elements sorted?

hard

A. Swap elements only if arr1[i] is greater than arr2[j] without sorting arr2

B. Use the gap method to compare and swap elements across arrays until fully merged

C. Sort both arrays separately and then concatenate

D. Copy all elements to a new array, sort it, then copy back

Solution

1. Step 1: Understand the gap method for merging

   The gap method reduces the gap between compared elements and swaps if needed, working across both arrays without extra space.

2. Step 2: Apply gap method to given arrays

   By repeatedly comparing and swapping elements at the gap distance, arr1 will hold the smallest elements and arr2 the larger ones, both sorted.

3. Final Answer:

   Use the gap method to compare and swap elements across arrays until fully merged -> Option B

4. Quick Check:

   Gap method merges sorted arrays in-place [OK]

Hint: Use gap method for in-place merge without extra space [OK]

Common Mistakes:

• Using extra arrays violating constraints
• Sorting arrays separately without merging
• Swapping without sorting arr2 leads to wrong order