Merge Two Sorted Arrays Without Extra Space in DSA C

Mental Model

We combine two sorted lists into one sorted order without using extra storage by swapping and sorting in place.

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

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: 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 ensure smaller elements stay in Array1 and larger in Array2 by swapping out-of-place elements.

Step 2: Sort Array1 and Array2 individually after swap

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

Why: Sorting each array restores order after swapping.

Step 3: 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 maintain sorted order across arrays.

Step 4: Sort Array1 and Array2 again

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

Why: Restore sorted order after swap.

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

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

Why: Final swap to ensure all smaller elements are in Array1.

Step 6: Sort Array1 and Array2 one last time

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

Why: Final sorted arrays without extra space.

Result:

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

Annotated Code

DSA C

#include <stdio.h>
#include <stdlib.h>

void sort_array(int *arr, int size) {
    for (int i = 0; i < size - 1; i++) {
        for (int j = 0; j < size - i - 1; j++) {
            if (arr[j] > arr[j + 1]) {
                int temp = arr[j];
                arr[j] = arr[j + 1];
                arr[j + 1] = temp;
            }
        }
    }
}

void merge_without_extra_space(int *arr1, int size1, int *arr2, int size2) {
    for (int i = 0; i < size1; i++) {
        if (arr1[size1 - 1] > arr2[0]) {
            int temp = arr1[size1 - 1];
            arr1[size1 - 1] = arr2[0];
            arr2[0] = temp;
            sort_array(arr1, size1);
            sort_array(arr2, size2);
        }
    }
}

void print_array(int *arr, int size) {
    for (int i = 0; i < size; i++) {
        printf("%d ", arr[i]);
    }
    printf("\n");
}

int main() {
    int arr1[] = {1, 5, 9, 10, 15, 20};
    int arr2[] = {2, 3, 8, 13};
    int size1 = sizeof(arr1) / sizeof(arr1[0]);
    int size2 = sizeof(arr2) / sizeof(arr2[0]);

    merge_without_extra_space(arr1, size1, arr2, size2);

    print_array(arr1, size1);
    print_array(arr2, size2);

    return 0;
}

if (arr1[size1 - 1] > arr2[0]) {

Check if last element of first array is greater than first element of second array to decide swap

int temp = arr1[size1 - 1]; arr1[size1 - 1] = arr2[0]; arr2[0] = temp;

Swap the out-of-place elements to maintain sorted order across arrays

sort_array(arr1, size1); sort_array(arr2, size2);

Sort both arrays after swap to restore order

Output

1 2 3 5 8 9 

10 13 15 20 

Complexity Analysis

Time: O(n * m * (n + m)) because for each element in first array we may swap and sort both arrays which costs O(n + m) each time

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

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

Edge Cases

One or both arrays are empty

No swaps or sorting needed, arrays remain as is

DSA C

for (int i = 0; i < size1; i++) { if (arr1[size1 - 1] > arr2[0]) { ... } }

Arrays already fully sorted with no overlapping values

No swaps occur, arrays remain unchanged

DSA C

if (arr1[size1 - 1] > arr2[0]) {

Arrays with duplicate values

Duplicates are handled naturally by sorting after swaps

DSA C

sort_array(arr1, size1); sort_array(arr2, size2);

When to Use This Pattern

When asked to merge two sorted arrays without extra space, use swapping and in-place sorting to maintain order without additional memory.

Common Mistakes

Mistake: Trying to merge by shifting elements manually without sorting after swaps
Fix: Always sort both arrays after swapping to restore sorted order

Mistake: Not comparing last element of first array with first element of second array
Fix: Compare arr1[size1 - 1] with arr2[0] to find out-of-place elements

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 out-of-place elements between arrays and then sort each array to maintain order.

Practice

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

easy

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

B. Sort each array separately using extra memory

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 task is 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 without allocating extra memory.

3. Final Answer:

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

4. Quick Check:

   Merge without extra space = Combine in place [OK]

Hint: Merge by swapping elements, no extra array needed [OK]

Common Mistakes:

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

2. Which of the following C code snippets correctly declares two sorted arrays for merging without extra space?

easy

A. int arr1[] = (1, 3, 5); int arr2[] = (2, 4, 6);

B. int arr1 = {1, 3, 5}; int arr2 = {2, 4, 6};

C. int arr1[] = [1, 3, 5]; int arr2[] = [2, 4, 6];

D. int arr1[] = {1, 3, 5}; int arr2[] = {2, 4, 6};

Solution

1. Step 1: Check array declaration syntax in C

   Arrays in C are declared using curly braces {} with type and square brackets [].

2. Step 2: Validate each option

   int arr1[] = {1, 3, 5}; int arr2[] = {2, 4, 6}; uses correct syntax: int arr[] = {elements}; Options A, B, and D use invalid syntax for arrays in C.

3. Final Answer:

   int arr1[] = {1, 3, 5}; int arr2[] = {2, 4, 6}; -> Option D

4. Quick Check:

   C arrays use {} for initialization [OK]

Hint: Use curly braces {} to initialize arrays in C [OK]

Common Mistakes:

• Using parentheses () or square brackets [] for initialization
• Missing data type or brackets
• Assigning arrays without braces

3. Given two sorted arrays:
arr1 = {1, 4, 7, 8, 10}
arr2 = {2, 3, 9}
After merging without extra space, what will be the content of arr1?

medium

A. [1, 2, 3, 4, 8]

B. [1, 2, 3, 4, 7]

C. [1, 2, 3, 7, 8]

D. [1, 3, 4, 7, 8]

Solution

1. Step 1: Understand merging without extra space

   We merge by comparing elements and swapping to keep smallest elements in arr1.

2. Step 2: Merge process

   Initial arr1: [1,4,7,8,10], arr2: [2,3,9]
   Compare 10 (arr1 last) and 2 (arr2 first), swap -> arr1: [1,4,7,8,2], arr2: [10,3,9]
   Sort arr2: [3,9,10]
   Repeat swaps and sorts until arr1 holds smallest 5 elements:
   Final arr1: [1,2,3,4,7]

3. Final Answer:

   [1, 2, 3, 4, 7] -> Option B

4. Quick Check:

   Smallest 5 elements in arr1 after merge = [1,2,3,4,7] [OK]

Hint: Keep smallest elements in first array by swapping [OK]

Common Mistakes:

• Not sorting arr2 after swaps
• Assuming arr1 remains unchanged
• Mixing elements without sorting

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;
    sort(arr2, arr2 + m);
  }
}

medium

A. Using sort() without including <algorithm> header

B. Swapping elements incorrectly between arrays

C. Sorting arr2 inside the loop causes inefficiency

D. Loop should run from 0 to m instead of n

Solution

1. Step 1: Analyze the loop and sorting

   The code swaps elements and sorts arr2 inside the loop for every iteration.

2. Step 2: Identify inefficiency

   Sorting arr2 in every iteration is costly and inefficient; better to optimize sorting or use a different approach.

3. Final Answer:

   Sorting arr2 inside the loop causes inefficiency -> Option C

4. Quick Check:

   Sorting inside loop = inefficient [OK]

Hint: Avoid sorting inside loops for better performance [OK]

Common Mistakes:

• Ignoring performance impact of repeated sorting
• Confusing array sizes for loop limits
• Assuming swap logic is incorrect

5. You have two sorted arrays:
arr1 = {1, 5, 9, 10, 15, 20}
arr2 = {2, 3, 8, 13}
Using the gap method to merge without extra space, what is the final state of arr2 after merging?

hard

A. [10, 13, 15, 20]

B. [8, 9, 10, 15]

C. [8, 13, 15, 20]

D. [9, 10, 13, 15]

Solution

1. Step 1: Understand the gap method

   The gap method compares elements at a gap distance and swaps if out of order, reducing gap until 1.

2. Step 2: Apply gap method to arrays

   Initial arr1: [1,5,9,10,15,20], arr2: [2,3,8,13]
   After merging, arr1 holds smallest elements: [1,2,3,5,8,9]
   arr2 holds remaining elements: [10,13,15,20]

3. Step 3: Final arr2 state

   arr2 after merge is [10, 13, 15, 20].

4. Final Answer:

   [10, 13, 15, 20] -> Option A

5. Quick Check:

   Gap method final arr2 = [10, 13, 15, 20] [OK]

Hint: Gap method sorts by comparing distant elements [OK]

Common Mistakes:

• Confusing final positions of elements in arr2
• Assuming arr2 remains unchanged
• Misapplying gap calculation