Merge Two Sorted Arrays Without Extra Space in DSA Go - 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 A's last and B's first

↓

Sort array B to keep it sorted

↓

Repeat until no swaps needed

↓

Done: Both arrays sorted, merged without extra space

We repeatedly swap the largest element of the first array with the smallest element of the second array if needed, then sort the second array to maintain order, until both arrays are merged in sorted order without extra space.

Execution Sample

DSA Go

A := []int{1, 5, 9, 10, 15, 20}
B := []int{2, 3, 8, 13}
for i := len(A)-1; i >= 0; i-- {
  if A[i] > B[0] {
    A[i], B[0] = B[0], A[i]
    sort.Ints(B)
  }
}

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

Execution Table

Step	Operation	A Array	B Array	Pointer Changes	Visual State
1	Compare A[5]=20 and B[0]=2	[1,5,9,10,15,20]	[2,3,8,13]	i=5	A:1->5->9->10->15->20 B:2->3->8->13
2	20 > 2, swap A[5] and B[0]	[1,5,9,10,15,2]	[20,3,8,13]	Swap A[5]<->B[0]	A:1->5->9->10->15->2 B:20->3->8->13
3	Sort B	[1,5,9,10,15,2]	[3,8,13,20]	B sorted	A:1->5->9->10->15->2 B:3->8->13->20
4	Compare A[4]=15 and B[0]=3	[1,5,9,10,15,2]	[3,8,13,20]	i=4	A:1->5->9->10->15->2 B:3->8->13->20
5	15 > 3, swap A[4] and B[0]	[1,5,9,10,3,2]	[15,8,13,20]	Swap A[4]<->B[0]	A:1->5->9->10->3->2 B:15->8->13->20
6	Sort B	[1,5,9,10,3,2]	[8,13,15,20]	B sorted	A:1->5->9->10->3->2 B:8->13->15->20
7	Compare A[3]=10 and B[0]=8	[1,5,9,10,3,2]	[8,13,15,20]	i=3	A:1->5->9->10->3->2 B:8->13->15->20
8	10 > 8, swap A[3] and B[0]	[1,5,9,8,3,2]	[10,13,15,20]	Swap A[3]<->B[0]	A:1->5->9->8->3->2 B:10->13->15->20
9	Sort B	[1,5,9,8,3,2]	[10,13,15,20]	B sorted	A:1->5->9->8->3->2 B:10->13->15->20
10	Compare A[2]=9 and B[0]=10	[1,5,9,8,3,2]	[10,13,15,20]	i=2	A:1->5->9->8->3->2 B:10->13->15->20
11	9 > 10? No	[1,5,9,8,3,2]	[10,13,15,20]	No swap	Arrays merged
12	End loop	[1,5,9,8,3,2]	[10,13,15,20]	i=-1	Done

💡 Loop ends when i < 0, no more elements in A to compare

Variable Tracker

Variable	Start	After Step 2	After Step 3	After Step 5	After Step 6	After Step 8	After Step 9	After Step 11	Final
A	[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]
B	[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	5	5	5	4	4	3	3	2	-1

Key Moments - 3 Insights

Why do we sort array B after swapping elements?

After swapping, B's first element may be larger than others, so sorting B keeps it sorted. See steps 3, 6, and 9 in execution_table where B is sorted after swaps.

Why do we compare A's last element with B's first element?

Because A and B are sorted, the largest element in A is at the end, and the smallest in B is at the start. Swapping these if needed moves bigger elements to B and smaller to A, gradually merging arrays. See steps 1, 4, 7, 10.

What stops the loop from running forever?

The loop runs from the last index of A down to 0. When i becomes -1, the loop ends as shown in step 12.

Visual Quiz - 3 Questions

Look at the execution_table at step 5, what is the state of array A?

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

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

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

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

💡 Hint

Check the 'A Array' column at step 5 in execution_table

At which step does the condition 'A[i] > B[0]' become false for the first time?

A Step 8

B Step 11

C Step 10

D Step 12

💡 Hint

Look at the 'Operation' and 'A Array' vs 'B Array' comparison in execution_table rows

If we skip sorting B after swapping, what will happen to the arrays?

A Array B becomes unsorted

B Arrays remain sorted

C Array A becomes unsorted

D Both arrays become empty

💡 Hint

Refer to key_moments about why sorting B is necessary after swaps

Concept Snapshot

Merge Two Sorted Arrays Without Extra Space:
- Compare last element of A with first of B
- If A's element > B's, swap them
- Sort B to maintain order
- Repeat for all elements in A
- Result: Both arrays sorted 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 element in the first array is bigger, we swap it with the smaller element in the second array. Then we sort the second array to keep it sorted. We repeat this process for each element in the first array from the end to the start. This way, the arrays gradually become merged and sorted without needing extra memory. The process stops when all elements in the first array have been checked. This method is efficient for memory and keeps both arrays sorted in place.

Practice

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

easy

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

B. Sort each array separately using extra space

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 single sorted sequence without using extra space, meaning no new arrays should be created.

2. Step 2: Identify the correct approach

   Only Combine both arrays into one sorted sequence without using extra memory describes merging both arrays into one sorted sequence without extra memory, which matches the problem's goal.

3. Final Answer:

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

4. Quick Check:

   Merge without extra space = Combine sorted arrays in place [OK]

Hint: Remember: no extra space means no new arrays [OK]

Common Mistakes:

• Thinking extra arrays are allowed
• Sorting arrays separately without merging
• Copying elements without sorting

2. Which of the following Go code snippets correctly swaps two elements a[i] and b[j] without extra space?

easy

A. a[i] = a[i] + b[j]; b[j] = a[i] - b[j]; a[i] = a[i] - b[j]

B. temp := a[i]; a[i] = b[j]; b[j] = temp

C. a[i] = b[j]; b[j] = a[i]

D. a[i], b[j] = b[j], a[i]

Solution

1. Step 1: Check Go syntax for swapping

   In Go, swapping two variables can be done directly using multiple assignment: a[i], b[j] = b[j], a[i].

2. Step 2: Analyze each option

   a[i], b[j] = b[j], a[i] uses correct Go syntax. temp := a[i]; a[i] = b[j]; b[j] = temp uses a temporary variable which is valid but uses extra space. a[i] = b[j]; b[j] = a[i] overwrites a[i] before assigning b[j]. a[i] = a[i] + b[j]; b[j] = a[i] - b[j]; a[i] = a[i] - b[j] uses arithmetic swap which is error-prone and not recommended.

3. Final Answer:

   a[i], b[j] = b[j], a[i] -> Option D

4. Quick Check:

   Go swap syntax = a[i], b[j] = b[j], a[i] [OK]

Hint: Use Go's multiple assignment for clean swaps [OK]

Common Mistakes:

• Overwriting values before swapping
• Using temp variables when avoiding extra space
• Using arithmetic swaps that can cause errors

3. What is the output of the following Go code after merging two sorted arrays without extra space?

arr1 := []int{1, 5, 9, 10, 15, 20}
arr2 := []int{2, 3, 8, 13}

for i := 0; i < len(arr1); i++ {
    if arr1[i] > arr2[0] {
        arr1[i], arr2[0] = arr2[0], arr1[i]
        // Re-sort arr2's first element
        first := arr2[0]
        k := 1
        for k < len(arr2) && arr2[k] < first {
            arr2[k-1] = arr2[k]
            k++
        }
        arr2[k-1] = first
    }
}

fmt.Println(arr1)
fmt.Println(arr2)

medium

A. [1 2 3 5 8 9]
[10 13 15 20]

B. [1 2 3 5 8 9]
[20 13 15 10]

C. [1 2 3 5 8 9 10 13 15 20]
[]

D. [1 2 3 5 9 10]
[8 13 15 20]

Solution

1. Step 1: Understand the merging logic

   The code compares each element of arr1 with the first element of arr2. If arr1[i] is greater, it swaps and then re-sorts arr2's first element to maintain sorted order.

2. Step 2: Trace the arrays after merging

   After the loop, arr1 becomes [1 2 3 5 8 9] and arr2 becomes [10 13 15 20]. The code does not combine arrays but rearranges elements to keep both sorted without extra space.

3. Final Answer:

   [1 2 3 5 8 9] [10 13 15 20] -> Option A

4. Quick Check:

   In-place merge = arr1 and arr2 sorted separately [OK]

Hint: Swap and re-sort arr2's first element to keep order [OK]

Common Mistakes:

• Assuming arrays combine into one
• Not re-sorting arr2 after swap
• Confusing output format

4. Identify the bug in this Go code snippet that tries to merge two sorted arrays without extra space:

for i := 0; i < len(arr1); i++ {
    if arr1[i] > arr2[0] {
        arr1[i], arr2[0] = arr2[0], arr1[i]
        for j := 0; j < 2; j++ {
            if arr2[j] > arr2[j+1] {
                arr2[j], arr2[j+1] = arr2[j+1], arr2[j]
            }
        }
    }
}

medium

A. The outer loop should iterate over arr2 instead of arr1

B. Swapping arr1[i] and arr2[0] is incorrect

C. The inner loop does not fully sort arr2 after swapping

D. The code uses extra space for swapping

Solution

1. Step 1: Analyze the sorting of arr2 after swap

   The inner loop only runs once per swap and performs a single pass of adjacent swaps, which is not enough to fully sort arr2.

2. Step 2: Identify the bug

   Because arr2 is not fully sorted after swapping, the merge will fail to maintain sorted order. A full re-sort or a proper insertion step is needed.

3. Final Answer:

   The inner loop does not fully sort arr2 after swapping -> Option C

4. Quick Check:

   Partial sort after swap causes incorrect order [OK]

Hint: Ensure full re-sort or insertion after swapping [OK]

Common Mistakes:

• Assuming one pass sorts arr2
• Swapping incorrectly
• Looping over wrong array

5. Given two sorted arrays arr1 = [1, 4, 7, 8, 10] and 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 elements sorted? Choose the correct final state of arr1 and arr2.

hard

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

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

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

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

Solution

1. Step 1: Merge by comparing and swapping elements

   Compare elements from arr1 and arr2. Swap if arr1[i] > arr2[0], then re-sort arr2 to keep it sorted.

2. Step 2: Final arrays after merging

   After merging, arr1 holds the smallest 5 elements: [1, 2, 3, 4, 7], and arr2 holds the remaining sorted elements: [8, 9, 10].

3. Final Answer:

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

4. Quick Check:

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

Hint: Swap and re-sort arr2's first element after each swap [OK]

Common Mistakes:

• Not re-sorting arr2 after swaps
• Mixing order of elements in arr2
• Assuming arr1 grows beyond its size