Merge Two Sorted Arrays Without Extra Space in DSA C++

Mental Model

We want to combine two sorted lists into one sorted order without using extra space. We do this by swapping elements between the two lists to keep them sorted.

Analogy: Imagine you have 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]
Pointers: ↑           ↑
           ↑           ↑

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: Compare last element of Array1 (20) with first element of Array2 (2), swap because 20 > 2

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

Why: We want smaller elements in Array1 and larger in Array2 to maintain sorted order.

Step 2: Sort Array2 after swap: Array2 becomes [3, 8, 13, 20]

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

Why: Sorting Array2 keeps it sorted after the swap.

Step 3: Sort Array1 after swap: Array1 becomes [1, 2, 5, 9, 10, 15]

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

Why: Sorting Array1 keeps it sorted after the swap.

Step 4: Compare last element of Array1 (15) with first element of Array2 (3), swap because 15 > 3

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

Why: Continue swapping to ensure smaller elements are in Array1.

Step 5: Sort Array2: [8, 13, 15, 20]

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

Why: Keep Array2 sorted after swap.

Step 6: Sort Array1: [1, 2, 3, 5, 9, 10]

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

Why: Keep Array1 sorted after swap.

Step 7: Compare last element of Array1 (10) with first element of Array2 (8), swap because 10 > 8

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

Why: Swap to maintain sorted order.

Step 8: Sort Array2 remains [10, 13, 15, 20], no swap needed now

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

Why: Arrays are now fully sorted without extra space.

Step 9: Sort Array1: [1, 2, 3, 5, 8, 9]

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

Why: Keep Array1 sorted after swap.

Result:

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

Annotated Code

DSA C++

#include <iostream>
#include <algorithm>
#include <vector>

void mergeWithoutExtraSpace(std::vector<int>& arr1, std::vector<int>& arr2) {
    int n = arr1.size();
    int m = arr2.size();

    for (int i = n - 1; i >= 0; i--) {
        if (arr1[i] > arr2[0]) {
            std::swap(arr1[i], arr2[0]);
            std::sort(arr2.begin(), arr2.end());
        }
    }
    std::sort(arr1.begin(), arr1.end());
}

int main() {
    std::vector<int> arr1 = {1, 5, 9, 10, 15, 20};
    std::vector<int> arr2 = {2, 3, 8, 13};

    mergeWithoutExtraSpace(arr1, arr2);

    for (int num : arr1) std::cout << num << " ";
    std::cout << std::endl;
    for (int num : arr2) std::cout << num << " ";
    std::cout << std::endl;

    return 0;
}

for (int i = n - 1; i >= 0; i--) {

iterate backward through arr1 to compare largest elements first

if (arr1[i] > arr2[0]) {

check if current element in arr1 is bigger than smallest in arr2

std::swap(arr1[i], arr2[0]);

swap to move smaller element into arr1 and bigger into arr2

std::sort(arr2.begin(), arr2.end());

sort arr2 to maintain its sorted order after swap

std::sort(arr1.begin(), arr1.end());

final sort of arr1 after all swaps to maintain sorted order

Output

1 2 3 5 8 9 

10 13 15 20 

Complexity Analysis

Time: O(n * m log m + n log n) because for each element in arr1 we may sort arr2 (m log m), then sort arr1 once (n log n)

Space: O(1) because no extra arrays are used, only swaps and in-place sorting

vs Alternative: Naive approach uses extra space O(n+m) to merge and then sort, which is simpler but uses more memory.

Edge Cases

One or both arrays empty

Function handles gracefully, no swaps or sorts needed

DSA C++

for (int i = n - 1; i >= 0; i--) {

Arrays already fully sorted with no overlapping elements

No swaps occur, arrays remain unchanged

DSA C++

if (arr1[i] > arr2[0]) {

Arrays with duplicate elements

Duplicates are preserved and sorted correctly

DSA C++

std::sort(arr2.begin(), arr2.end());

When to Use This Pattern

When asked to merge two sorted arrays without extra space, reach for the swapping and in-place sorting pattern to maintain order without extra memory.

Common Mistakes

Mistake: Not sorting the second array after swapping, causing it to become unsorted
Fix: Always sort the second array after swapping to keep it sorted.

Summary

Merges two sorted arrays into sorted order without using extra space by swapping and sorting in place.

Use when memory is limited and you cannot allocate extra arrays for merging.

The key insight is to swap larger elements from the first array with smaller elements from the second, then sort the second array to maintain order.

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