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 A and B

↓

Compare last element of A with first element of B

↓

If A's last > B's first, swap them

↓

Sort both arrays individually

↓

Repeat until no swaps needed

↓

Arrays merged without extra space

We repeatedly compare and swap elements between the two arrays to ensure all smaller elements are in the first array and larger in the second, then sort both arrays until fully merged.

Execution Sample

DSA C#

int[] A = {1, 5, 9, 10, 15, 20};
int[] B = {2, 3, 8, 13};
// Merge without extra space
while (A[A.Length - 1] > B[0]) {
  int temp = A[A.Length - 1];
  A[A.Length - 1] = B[0];
  B[0] = temp;
  Array.Sort(A);
  Array.Sort(B);
}

This code merges two sorted arrays A and B without extra space by swapping and sorting repeatedly.

Execution Table

Step	Operation	Array A	Array B	Pointer Changes	Visual State
1	Initial arrays	[1, 5, 9, 10, 15, 20]	[2, 3, 8, 13]	None	A: 1->5->9->10->15->20 B: 2->3->8->13
2	Compare A last (20) > B first (2)? Yes	Same	Same	Pointers at A[5], B[0]	A last=20, B first=2
3	Swap A last and B first	[1, 5, 9, 10, 15, 2]	[20, 3, 8, 13]	Swapped A[5]<->B[0]	A: 1->5->9->10->15->2 B: 20->3->8->13
4	Sort A	[1, 2, 5, 9, 10, 15]	Same	Sorted A	A: 1->2->5->9->10->15 B: 20->3->8->13
5	Sort B	Same	[3, 8, 13, 20]	Sorted B	A: 1->2->5->9->10->15 B: 3->8->13->20
6	Compare A last (15) > B first (3)? Yes	Same	Same	Pointers at A[5], B[0]	A last=15, B first=3
7	Swap A last and B first	[1, 2, 5, 9, 10, 3]	[15, 8, 13, 20]	Swapped A[5]<->B[0]	A: 1->2->5->9->10->3 B: 15->8->13->20
8	Sort A	[1, 2, 3, 5, 9, 10]	Same	Sorted A	A: 1->2->3->5->9->10 B: 15->8->13->20
9	Sort B	Same	[8, 13, 15, 20]	Sorted B	A: 1->2->3->5->9->10 B: 8->13->15->20
10	Compare A last (10) > B first (8)? Yes	Same	Same	Pointers at A[5], B[0]	A last=10, B first=8
11	Swap A last and B first	[1, 2, 3, 5, 9, 8]	[10, 13, 15, 20]	Swapped A[5]<->B[0]	A: 1->2->3->5->9->8 B: 10->13->15->20
12	Sort A	[1, 2, 3, 5, 8, 9]	Same	Sorted A	A: 1->2->3->5->8->9 B: 10->13->15->20
13	Sort B	Same	[10, 13, 15, 20]	Sorted B	A: 1->2->3->5->8->9 B: 10->13->15->20
14	Compare A last (9) > B first (10)? No	Same	Same	No swap needed	Final merged arrays
15	End	Final arrays merged	Final arrays merged	No changes	A: 1->2->3->5->8->9 B: 10->13->15->20

💡 No swap needed as last element of A (9) is not greater than first element of B (10)

Variable Tracker

Variable	Start	After Step 3	After Step 7	After Step 11	Final
Array A	[1,5,9,10,15,20]	[1,5,9,10,15,2]	[1,2,5,9,10,3]	[1,2,3,5,8,9]	[1,2,3,5,8,9]
Array B	[2,3,8,13]	[20,3,8,13]	[15,8,13,20]	[10,13,15,20]	[10,13,15,20]
Pointers	None	A[5], B[0]	A[5], B[0]	A[5], B[0]	None

Key Moments - 3 Insights

Why do we swap only the last element of A with the first element of B?

Because both arrays are sorted, the largest element in A is at the end and the smallest in B is at the start. Swapping these ensures smaller elements stay in A and larger in B, as shown in steps 2, 6, and 10.

Why do we sort both arrays after each swap?

Swapping can break the sorted order. Sorting both arrays after swap restores order, ensuring the next comparison is valid. This is seen in steps 4, 5, 8, 9, 12, and 13.

When does the merging process stop?

When the last element of A is not greater than the first element of B, meaning no more swaps are needed. This happens at step 14.

Visual Quiz - 3 Questions

Look at the execution table, what is the state of Array A after step 8?

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

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

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

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

💡 Hint

Check the 'Array A' column in the execution_table row for step 8.

At which step does the condition 'A last > B first' become false, stopping the loop?

A Step 10

B Step 12

C Step 14

D Step 15

💡 Hint

Look at the 'Operation' and 'Exit Note' in the execution_table for when no swap is needed.

If we did not sort arrays after swapping, what would happen to the visual state at step 5?

A Array A would be unsorted

B Both arrays could be unsorted

C Array B would be unsorted

D Arrays would remain sorted

💡 Hint

Refer to key_moments explaining why sorting after swap is necessary.

Concept Snapshot

Merge Two Sorted Arrays Without Extra Space:
- Compare last element of A with first of B
- If A last > B first, swap them
- Sort both arrays after swap
- 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 last element of the first array is greater, we swap it with the first element of the second array. After swapping, both arrays are sorted again to maintain order. This process repeats until the last element of the first array is not greater than the first element of the second array. The arrays are then merged in sorted order without using extra memory.

Practice

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

easy

A. Create a new array to hold merged elements

B. Combine both arrays into one sorted sequence without using extra memory

C. Copy elements from one array to another without sorting

D. Sort each array separately using extra space

Solution

1. Step 1: Understand the problem requirement

   The task is to merge two sorted arrays so that the combined elements remain sorted, but without using any extra space like a new array.

2. Step 2: Identify the correct approach

   We must rearrange elements within the given arrays themselves to maintain sorted order 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 between arrays without extra space [OK]

Common Mistakes:

• Assuming extra space is allowed
• Sorting arrays separately without merging
• Creating a new array for merged result

2. Which of the following C# code snippets correctly swaps elements between two arrays without extra space?

easy

A. arr1[i] = arr1[i] + arr2[j]; arr2[j] = arr1[i] - arr2[j]; arr1[i] = arr1[i] - arr2[j];

B. arr1[i] = arr2[j]; arr2[j] = arr1[i];

C. if (arr1[i] > arr2[j]) { int temp = arr1[i]; arr1[i] = arr2[j]; arr2[j] = temp; }

D. int temp = arr2[j]; arr2[j] = arr1[i]; arr1[i] = temp + 1;

Solution

1. Step 1: Check swapping logic correctness

   if (arr1[i] > arr2[j]) { int temp = arr1[i]; arr1[i] = arr2[j]; arr2[j] = temp; } uses a temporary variable to swap values correctly without losing data.

2. Step 2: Analyze other options for errors

   arr1[i] = arr2[j]; arr2[j] = arr1[i]; overwrites arr2[j] before saving arr1[i], losing original value. arr1[i] = arr1[i] + arr2[j]; arr2[j] = arr1[i] - arr2[j]; arr1[i] = arr1[i] - arr2[j]; uses arithmetic swap but can cause overflow and is less safe. int temp = arr2[j]; arr2[j] = arr1[i]; arr1[i] = temp + 1; incorrectly adds 1 during swap, changing values.

3. Final Answer:

   if (arr1[i] > arr2[j]) { int temp = arr1[i]; arr1[i] = arr2[j]; arr2[j] = temp; } -> Option C

4. Quick Check:

   Temporary variable swap = Correct swap [OK]

Hint: Use a temp variable to swap safely in C# [OK]

Common Mistakes:

• Overwriting values without temp variable
• Using unsafe arithmetic swaps
• Altering values unintentionally during swap

3. What will be the content of arrays after running this code?

int[] arr1 = {1, 5, 9, 10, 15, 20};
int[] arr2 = {2, 3, 8, 13};
int n = arr1.Length, m = arr2.Length;
for (int i = 0; i < n; i++) {
  if (arr1[i] > arr2[0]) {
    int temp = arr1[i];
    arr1[i] = arr2[0];
    arr2[0] = temp;
    int first = arr2[0];
    int k;
    for (k = 1; k < m && arr2[k] < first; k++) {
      arr2[k - 1] = arr2[k];
    }
    arr2[k - 1] = first;
  }
}

medium

A. arr1 = [1, 2, 3, 5, 9, 10], arr2 = [8, 13, 15, 20]

B. arr1 = [1, 3, 5, 8, 9, 10], arr2 = [2, 13, 15, 20]

C. arr1 = [1, 2, 5, 8, 9, 10], arr2 = [3, 13, 15, 20]

D. arr1 = [1, 2, 3, 5, 8, 9], arr2 = [10, 13, 15, 20]

Solution

1. Step 1: Trace the swapping and insertion in arr2

   For each element in arr1, if it is greater than arr2[0], swap and then insert arr2[0] in sorted order in arr2. This pushes larger elements to arr2.

2. Step 2: Final arrays after all iterations

   After all swaps and insertions, arr1 becomes [1, 2, 3, 5, 8, 9] and arr2 becomes [10, 13, 15, 20].

3. Final Answer:

   arr1 = [1, 2, 3, 5, 8, 9], arr2 = [10, 13, 15, 20] -> Option D

4. Quick Check:

   In-place merge with insertion sort = arr1 and arr2 sorted [OK]

Hint: Swap if arr1[i] > arr2[0], then insert arr2[0] sorted [OK]

Common Mistakes:

• Not inserting arr2[0] correctly after swap
• Overwriting arr2 elements incorrectly
• Confusing array indices during insertion

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;
    int first = arr2[0];
    int k = 1;
    while (k < m && arr2[k] < first) {
      arr2[k - 1] = arr2[k];
      k++;
    }
    arr2[k] = first;
  }
}

medium

A. The insertion index in arr2 is incorrect; should be arr2[k - 1] = first

B. The swap logic between arr1[i] and arr2[0] is wrong

C. The loop should run from i = 1 instead of 0

D. The condition arr2[k] < first should be arr2[k] > first

Solution

1. Step 1: Analyze insertion logic in arr2

   The code shifts elements left to make space for 'first'. The correct insertion index after shifting is k - 1, not k.

2. Step 2: Identify the error impact

   Assigning arr2[k] = first overwrites the next element incorrectly, causing wrong order.

3. Final Answer:

   The insertion index in arr2 is incorrect; should be arr2[k - 1] = first -> Option A

4. Quick Check:

   Correct insertion index = k - 1 [OK]

Hint: Insert shifted element at k-1 index after loop ends [OK]

Common Mistakes:

• Using wrong index for insertion after shifting
• Incorrect swap logic
• Wrong loop start index

5. Given two sorted arrays:
arr1 = [1, 4, 7, 8, 10]
arr2 = [2, 3, 9]
How would you merge them without extra space so that after merging, arr1 contains the first 5 smallest elements and arr2 contains the remaining sorted elements? Choose the correct final arrays.

hard

A. arr1 = [1, 2, 3, 4, 7], arr2 = [8, 9, 10]

B. arr1 = [1, 3, 4, 7, 8], arr2 = [2, 9, 10]

C. arr1 = [1, 2, 4, 7, 8], arr2 = [3, 9, 10]

D. arr1 = [1, 2, 3, 4, 8], arr2 = [7, 9, 10]

Solution

1. Step 1: Compare and swap elements between arr1 and arr2

   Start from beginning of arr1, if arr1[i] > arr2[0], swap and then insert arr2[0] in sorted order in arr2.

2. Step 2: After all swaps and insertions

   arr1 becomes [1, 2, 3, 4, 7] and arr2 becomes [8, 9, 10], maintaining sorted order without extra space.

3. Final Answer:

   arr1 = [1, 2, 3, 4, 7], arr2 = [8, 9, 10] -> Option A

4. Quick Check:

   In-place merge keeps first array smallest elements [OK]

Hint: Swap if arr1[i] > arr2[0], then insert arr2[0] sorted [OK]

Common Mistakes:

• Not maintaining sorted order after swap
• Incorrect insertion in second array
• Assuming extra space is allowed