Merge Two Sorted Arrays Without Extra Space in DSA Go

Mental Model

We combine two sorted lists into one sorted order by swapping elements between them without using extra space.

Analogy: Imagine two sorted stacks of books on two tables. Instead of moving books to a new table, you swap books between the tables to keep both stacks sorted.

Array1: [1, 5, 9, 10, 15, 20]
Array2: [2, 3, 8, 13]

Dry Run Walkthrough

Input: Array1: [1, 5, 9, 10, 15, 20], Array2: [2, 3, 8, 13]

Goal: Merge both arrays so that all elements are sorted across both arrays without using extra space

Step 1: i=5: Compare arr1[5]=20 > arr2[0]=2, swap arr1[5] ↔ arr2[0]

Array1: [1, 5, 9, 10, 15, 2]
Array2: [20, 3, 8, 13]

Why: Move smaller element from arr2 to arr1; larger to arr2

Step 2: Sort arr2 to restore order

Array1: [1, 5, 9, 10, 15, 2]
Array2: [3, 8, 13, 20]

Why: arr2[0] must always be the smallest in arr2 for correct comparisons

Step 3: i=4: arr1[4]=15 > arr2[0]=3, swap arr1[4] ↔ arr2[0]

Array1: [1, 5, 9, 10, 3, 2]
Array2: [15, 8, 13, 20]

Why: Continue placing smaller elements into arr1 from the end

Step 4: Sort arr2

Array1: [1, 5, 9, 10, 3, 2]
Array2: [8, 13, 15, 20]

Why: Maintain arr2 sorted with arr2[0] as smallest

Step 5: i=3: arr1[3]=10 > arr2[0]=8, swap arr1[3] ↔ arr2[0]

Array1: [1, 5, 9, 8, 3, 2]
Array2: [10, 13, 15, 20]

Why: Swap to push small element into arr1

Step 6: Sort arr2

Array1: [1, 5, 9, 8, 3, 2]
Array2: [10, 13, 15, 20]

Why: Restore arr2 order

Step 7: i=2: arr1[2]=9 <= arr2[0]=10, no swap

Array1: [1, 5, 9, 8, 3, 2]
Array2: [10, 13, 15, 20]

Why: No need to swap as arr1[2] is smaller

Step 8: i=1: 5 <=10, no swap; i=0: 1<=10, no swap

Array1: [1, 5, 9, 8, 3, 2]
Array2: [10, 13, 15, 20]

Why: All remaining arr1 elements are smaller than arr2[0]

Step 9: After loop, sort arr1 to restore order

Array1: [1, 2, 3, 5, 8, 9]
Array2: [10, 13, 15, 20]

Why: arr1 now contains all smallest elements, sorting finalizes it

Result:

Array1: [1, 2, 3, 5, 8, 9]
Array2: [10, 13, 15, 20]

Annotated Code

DSA Go

package main

import (
	"fmt"
	"sort"
)

func mergeWithoutExtraSpace(arr1 []int, arr2 []int) {
	m := len(arr1)
	n := len(arr2)

	for i := m - 1; i >= 0; i-- {
		if arr1[i] > arr2[0] {
			// Swap
			arr1[i], arr2[0] = arr2[0], arr1[i]

			// Sort arr2 to maintain order
			sort.Ints(arr2)
		}
	}

	// Sort arr1 to maintain order after all swaps
	sort.Ints(arr1)
}

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

	mergeWithoutExtraSpace(arr1, arr2)

	// Print merged arrays
	for _, v := range arr1 {
		fmt.Printf("%d ", v)
	}
	fmt.Println()
	for _, v := range arr2 {
		fmt.Printf("%d ", v)
	}
	fmt.Println()
}

for i := m - 1; i >= 0; i-- {

Iterate backward through arr1 to handle largest elements first

if arr1[i] > arr2[0] {

Compare with current smallest in arr2 (after previous sorts)

arr1[i], arr2[0] = arr2[0], arr1[i]

Swap to move smaller from arr2 to arr1's end positions

sort.Ints(arr2)

Re-sort arr2 so arr2[0] is always the next smallest

sort.Ints(arr1)

Final sort on arr1 after all small elements are swapped in

Output

1 2 3 5 8 9 

10 13 15 20 

Complexity Analysis

Time: O(m * n log n) because up to m iterations, each potentially sorting arr2 in O(n log n)

Space: O(1) auxiliary space (in-place swaps and sorts)

vs Alternative: Standard merge uses O(m+n) time and space; optimal in-place is O(m+n) time with gap method, but this is simple with sorting

Edge Cases

One or both arrays empty

Loop doesn't run or no swaps; final sort on arr1 if needed

DSA Go

len checks implicit in loop; sort handles empty

arr1 shorter than arr2

May not fully merge correctly as small elements only swapped into arr1 up to its size

DSA Go

Assumes len(arr1) >= len(arr2); add check if needed

Arrays with duplicates

Handled correctly as comparisons are >, stable with sorts

DSA Go

sort.Ints is stable for equals

All elements in arr1 smaller than arr2

No swaps, just sort arr1 at end (already sorted)

DSA Go

if condition never true

When to Use This Pattern

For in-place merge of sorted arrays without extra space, use end-to-start swaps with repeated sorting of the smaller array.

Common Mistakes

Mistake: Forgetting to sort arr2 after each swap, causing arr2[0] not to be minimal
Fix: sort.Ints(arr2) immediately after swap

Mistake: Sorting arr1 inside the loop (unnecessary and inefficient)
Fix: Sort arr1 only once after the entire loop

Mistake: Iterating from start of arr1 instead of end
Fix: Start from i = m-1 to prioritize displacing largest elements

Summary

Merges two sorted arrays in-place by swapping large elements from arr1 with small from arr2, sorting arr2 each time, and arr1 at end.

Ideal when space is critical but time can be traded (O(m n log n)).

Key: Backward iteration + post-swap sort on arr2 ensures correct smallest element selection.

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