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

Merge Two Sorted Arrays Without Extra Space

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

🎯 Goal: Write a program to merge two sorted arrays arr1 and arr2 into a single sorted sequence without using extra space. The final sorted elements should be distributed between arr1 and arr2.

📋 What You'll Learn

Create two sorted arrays arr1 and arr2 with given values

Create variables to hold the sizes of arr1 and arr2

Implement the merge logic without using extra space

Print the final merged arrays

💡 Why This Matters

🌍 Real World

Merging sorted lists without extra space is useful in memory-limited devices or when working with large datasets where extra memory allocation is costly.

💼 Career

Understanding in-place merging techniques is valuable for software engineers working on embedded systems, database engines, or performance-critical applications.

1

Create two sorted arrays

Create two sorted arrays called arr1 and arr2 with these exact values: arr1 contains 1, 5, 9, 10, 15, 20 and arr2 contains 2, 3, 8, 13. Also create integer variables n and m to store the sizes of arr1 and arr2 respectively.

DSA C

# Your code here

Hint

Use array initialization syntax and assign sizes to n and m.

2

Set up index variables for merging

Create three integer variables called i, j, and k. Initialize i to n - 1, j to 0, and k to 0. These will help in merging the arrays without extra space.

DSA C

int arr1[] = {1, 5, 9, 10, 15, 20};
int arr2[] = {2, 3, 8, 13};
int n = 6;
int m = 4;
// Your code here

Hint

Initialize i to the last index of arr1, j to the first index of arr2, and k to zero.

3

Merge arrays without extra space

Use a while loop with the condition i >= 0 && j < m. Inside the loop, compare arr1[i] and arr2[j]. If arr1[i] is greater, swap arr1[i] and arr2[j]. Then decrement i and increment j. After the loop, sort both arrays using a simple sorting method like bubble sort.

DSA C

int arr1[] = {1, 5, 9, 10, 15, 20};
int arr2[] = {2, 3, 8, 13};
int n = 6;
int m = 4;
int i = n - 1;
int j = 0;
int k = 0;
// Your code here

Hint

Swap elements when arr1[i] is bigger, then sort both arrays to finalize the merge.

4

Print the merged arrays

Use two for loops to print the elements of arr1 and arr2 separated by spaces. Print arr1 elements first, then print a newline, then print arr2 elements.

DSA C

int arr1[] = {1, 5, 9, 10, 15, 20};
int arr2[] = {2, 3, 8, 13};
int n = 6;
int m = 4;
int i = n - 1;
int j = 0;
int k = 0;

while (i >= 0 && j  arr2[j]) {
        int temp = arr1[i];
        arr1[i] = arr2[j];
        arr2[j] = temp;
    }
    i--;
    j++;
}

// Bubble sort for arr1
for (int x = 0; x  arr1[y + 1]) {
            int temp = arr1[y];
            arr1[y] = arr1[y + 1];
            arr1[y + 1] = temp;
        }
    }
}

// Bubble sort for arr2
for (int x = 0; x  arr2[y + 1]) {
            int temp = arr2[y];
            arr2[y] = arr2[y + 1];
            arr2[y + 1] = temp;
        }
    }
}
// Your code here

Hint

Print all elements of arr1 separated by spaces, then a newline, then all elements of arr2.

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