Merge Two Sorted Arrays Without Extra Space in DSA Go - Build from Scratch

Merge Two Sorted Arrays Without Extra Space

📖 Scenario: You have two sorted lists of numbers representing two separate shelves of books arranged by height. You want to merge these two shelves into one sorted order without using extra space, so you can organize the books efficiently without needing a new shelf.

🎯 Goal: Build a Go program that merges two sorted integer arrays arr1 and arr2 into sorted order without using extra space. The final sorted numbers should be split between arr1 and arr2 such that all smaller numbers are in arr1 and the rest in arr2.

📋 What You'll Learn

Create two sorted integer arrays arr1 and arr2 with exact values

Create an integer variable n for the length of arr1

Write a function mergeWithoutExtraSpace(arr1 []int, arr2 []int, n int) that merges the arrays in place

Print the final state of arr1 and arr2 after merging

💡 Why This Matters

🌍 Real World

Merging sorted lists without extra space is useful when memory is limited, such as in embedded systems or when working with large datasets.

💼 Career

Understanding in-place merging helps in optimizing algorithms and is a common interview question for software engineering roles.

1

Create two sorted arrays

Create two sorted integer arrays called arr1 with values 1, 5, 9, 10, 15, 20 and arr2 with values 2, 3, 8, 13.

DSA Go

# Create two sorted arrays arr1 and arr2 with given values
# Your code here

Hint

Use arr1 := []int{1, 5, 9, 10, 15, 20} and arr2 := []int{2, 3, 8, 13} to create the arrays.

2

Create length variable for arr1

Create an integer variable called n and set it to the length of arr1 using len(arr1).

DSA Go

package main

import "fmt"

func main() {
    arr1 := []int{1, 5, 9, 10, 15, 20}
    arr2 := []int{2, 3, 8, 13}
    // Create variable n for length of arr1
    // Your code here
}

Hint

Use n := len(arr1) to get the length of arr1.

3

Write merge function without extra space

Write a function called mergeWithoutExtraSpace that takes arr1 []int, arr2 []int, and n int as parameters. Inside it, use a for loop with variable i from 0 to n-1. For each i, compare arr1[i] and arr2[0]. If arr1[i] is greater, swap them. Then sort arr2 to keep it sorted by shifting the first element to its correct position. Call this function from main with arr1, arr2, and n.

DSA Go

package main

import "fmt"

func mergeWithoutExtraSpace(arr1 []int, arr2 []int, n int) {
    // Your code here
}

func main() {
    arr1 := []int{1, 5, 9, 10, 15, 20}
    arr2 := []int{2, 3, 8, 13}
    n := len(arr1)
    // Call mergeWithoutExtraSpace here
    // Your code here
}

Hint

Use a loop from 0 to n-1. Swap if arr1[i] > arr2[0]. Then shift arr2[0] to correct place to keep arr2 sorted.

4

Print the merged arrays

Print the final state of arr1 and arr2 using fmt.Println to show the merged sorted arrays.

DSA Go

package main

import "fmt"

func mergeWithoutExtraSpace(arr1 []int, arr2 []int, n int) {
    for i := 0; i  arr2[0] {
            arr1[i], arr2[0] = arr2[0], arr1[i]
            first := arr2[0]
            k := 1
            for k < len(arr2) && arr2[k] < first {
                arr2[k-1] = arr2[k]
                k++
            }
            arr2[k-1] = first
        }
    }
}

func main() {
    arr1 := []int{1, 5, 9, 10, 15, 20}
    arr2 := []int{2, 3, 8, 13}
    n := len(arr1)
    mergeWithoutExtraSpace(arr1, arr2, n)
    // Print arr1 and arr2
    // Your code here
}

Hint

Use fmt.Println(arr1) and fmt.Println(arr2) to print the arrays.

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