Why Merge Two Sorted Arrays Without Extra Space in DSA C?

The Big Idea

What if you could merge two sorted lists without needing any extra space at all?

The Scenario

Imagine you have two lists of numbers, each already sorted, and you want to combine them into one sorted list. Doing this by hand means writing down all numbers from both lists and then sorting them again, which takes a lot of time and effort.

The Problem

Manually combining and sorting two lists means you need extra space to hold all numbers together before sorting. This uses more memory and takes longer because you sort everything again, even though the lists were already sorted.

The Solution

This method smartly merges two sorted lists without needing extra space. It rearranges numbers between the two lists step by step, keeping them sorted as it goes, saving memory and time.

Before vs After

✗ Before

int merged[size1 + size2];
for (int i = 0; i < size1; i++) merged[i] = arr1[i];
for (int j = 0; j < size2; j++) merged[size1 + j] = arr2[j];
sort(merged, merged + size1 + size2);

✓ After

for (int i = 0; i < size1; i++) {
  if (arr1[i] > arr2[0]) {
    int temp = arr1[i];
    arr1[i] = arr2[0];
    arr2[0] = temp;
    // Re-sort arr2 to maintain sorted order
  }
}

What It Enables

You can merge two sorted lists efficiently without using extra memory, making programs faster and lighter.

Real Life Example

When your phone merges two contact lists from different apps without creating a big new list, saving space and keeping contacts sorted.

Key Takeaways

Manual merging wastes memory and time by copying and sorting all elements.

This method merges in place by swapping and sorting minimal parts.

It keeps both lists sorted without extra space.

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