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 comparing and 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 all books to a new table, you pick the smallest book from the second table and swap it with a bigger book from the first table to keep both stacks sorted.

Array1: [1] -> [5] -> [9] -> [10]
Array2: [2] -> [3] -> [8] -> [15]

Dry Run Walkthrough

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

Goal: Merge both arrays so that all elements are sorted across both arrays without using extra space

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

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

Why: We want smaller elements in Array1 and bigger in Array2 to keep arrays sorted after sorting

Step 2: Sort Array2 to fix order after swap

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

Why: Sorting Array2 restores sorted order after the swap

Step 3: Sort Array1 to fix order after swap

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

Why: Sorting Array1 restores sorted order after the swap

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

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

Why: Smaller elements should be in Array1, so swap to maintain order

Step 5: Sort Array2 again

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

Why: Restore sorted order in Array2 after swap

Step 6: Sort Array1 again

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

Why: Restore sorted order in Array1 after swap

Step 7: Compare last element of Array1 (5) with first element of Array2 (8), no swap needed because 5 < 8

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

Why: Arrays are now correctly merged without extra space

Result:

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

Annotated Code

DSA C#

using System;

class MergeSortedArrays {
    public static void Merge(int[] arr1, int[] arr2) {
        int n = arr1.Length;
        int m = arr2.Length;

        for (int i = n - 1; i >= 0; i--) {
            // Compare arr1[i] with first element of arr2
            if (arr1[i] > arr2[0]) {
                // Swap if arr1[i] is greater
                int temp = arr1[i];
                arr1[i] = arr2[0];
                arr2[0] = temp;

                // Sort arr2 to keep it sorted after swap
                Array.Sort(arr2);
            }
        }
        // Sort arr1 after all swaps to restore order
        Array.Sort(arr1);
    }

    public static void PrintArrays(int[] arr1, int[] arr2) {
        Console.WriteLine("Array1: " + string.Join(", ", arr1));
        Console.WriteLine("Array2: " + string.Join(", ", arr2));
    }

    static void Main() {
        int[] arr1 = {1, 5, 9, 10};
        int[] arr2 = {2, 3, 8, 15};

        Merge(arr1, arr2);
        PrintArrays(arr1, arr2);
    }
}

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

iterate backward through arr1 to compare larger elements first

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

check if current arr1 element is bigger than smallest arr2 element

int temp = arr1[i]; arr1[i] = arr2[0]; arr2[0] = temp;

swap elements to move smaller element into arr1

Array.Sort(arr2);

sort arr2 to restore sorted order after swap

Array.Sort(arr1);

sort arr1 after all swaps to restore sorted order

Output

Array1: 1, 2, 3, 5

Array2: 8, 9, 10, 15

Complexity Analysis

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

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

vs Alternative: Naive approach merges into a new array with O(n+m) space, this method saves space but is slower due to repeated sorting

Edge Cases

One or both arrays empty

No swaps or sorting needed, arrays remain unchanged

DSA C#

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

Arrays already fully merged (all elements in arr1 smaller than arr2)

No swaps occur, arrays remain unchanged

DSA C#

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

Arrays with duplicate elements

Duplicates are handled correctly by swaps and sorting

DSA C#

Array.Sort(arr2);

When to Use This Pattern

When asked to merge two sorted arrays without extra space, use the swapping and sorting approach to keep arrays sorted in place.

Common Mistakes

Mistake: Not sorting the second array after swapping, leading to incorrect order
Fix: Always sort the second array after swapping to maintain sorted order

Mistake: Not sorting the first array after all swaps, leading to incorrect order
Fix: Sort the first array after all swaps to restore sorted order

Mistake: Iterating forward through arr1 causing missed swaps
Fix: Iterate backward through arr1 to compare larger elements first

Summary

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

Use when you must merge sorted arrays but cannot use extra memory.

The key is to swap bigger elements from the first array with smaller from the second, then sort the second array to maintain order, and finally sort the first array.

Practice

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

easy

A. Create a new array to hold merged elements

B. Combine both arrays into one sorted sequence without using extra memory

C. Copy elements from one array to another without sorting

D. Sort each array separately using extra space

Solution

1. Step 1: Understand the problem requirement

   The task is to merge two sorted arrays so that the combined elements remain sorted, but without using any extra space like a new array.

2. Step 2: Identify the correct approach

   We must rearrange elements within the given arrays themselves to maintain sorted order without additional memory.

3. Final Answer:

   Combine both arrays into one sorted sequence without using extra memory -> Option B

4. Quick Check:

   Merge without extra space = Combine in place [OK]

Hint: Merge by swapping elements between arrays without extra space [OK]

Common Mistakes:

• Assuming extra space is allowed
• Sorting arrays separately without merging
• Creating a new array for merged result

2. Which of the following C# code snippets correctly swaps elements between two arrays without extra space?

easy

A. arr1[i] = arr1[i] + arr2[j]; arr2[j] = arr1[i] - arr2[j]; arr1[i] = arr1[i] - arr2[j];

B. arr1[i] = arr2[j]; arr2[j] = arr1[i];

C. if (arr1[i] > arr2[j]) { int temp = arr1[i]; arr1[i] = arr2[j]; arr2[j] = temp; }

D. int temp = arr2[j]; arr2[j] = arr1[i]; arr1[i] = temp + 1;

Solution

1. Step 1: Check swapping logic correctness

   if (arr1[i] > arr2[j]) { int temp = arr1[i]; arr1[i] = arr2[j]; arr2[j] = temp; } uses a temporary variable to swap values correctly without losing data.

2. Step 2: Analyze other options for errors

   arr1[i] = arr2[j]; arr2[j] = arr1[i]; overwrites arr2[j] before saving arr1[i], losing original value. arr1[i] = arr1[i] + arr2[j]; arr2[j] = arr1[i] - arr2[j]; arr1[i] = arr1[i] - arr2[j]; uses arithmetic swap but can cause overflow and is less safe. int temp = arr2[j]; arr2[j] = arr1[i]; arr1[i] = temp + 1; incorrectly adds 1 during swap, changing values.

3. Final Answer:

   if (arr1[i] > arr2[j]) { int temp = arr1[i]; arr1[i] = arr2[j]; arr2[j] = temp; } -> Option C

4. Quick Check:

   Temporary variable swap = Correct swap [OK]

Hint: Use a temp variable to swap safely in C# [OK]

Common Mistakes:

• Overwriting values without temp variable
• Using unsafe arithmetic swaps
• Altering values unintentionally during swap

3. What will be the content of arrays after running this code?

int[] arr1 = {1, 5, 9, 10, 15, 20};
int[] arr2 = {2, 3, 8, 13};
int n = arr1.Length, m = arr2.Length;
for (int i = 0; i < n; i++) {
  if (arr1[i] > arr2[0]) {
    int temp = arr1[i];
    arr1[i] = arr2[0];
    arr2[0] = temp;
    int first = arr2[0];
    int k;
    for (k = 1; k < m && arr2[k] < first; k++) {
      arr2[k - 1] = arr2[k];
    }
    arr2[k - 1] = first;
  }
}

medium

A. arr1 = [1, 2, 3, 5, 9, 10], arr2 = [8, 13, 15, 20]

B. arr1 = [1, 3, 5, 8, 9, 10], arr2 = [2, 13, 15, 20]

C. arr1 = [1, 2, 5, 8, 9, 10], arr2 = [3, 13, 15, 20]

D. arr1 = [1, 2, 3, 5, 8, 9], arr2 = [10, 13, 15, 20]

Solution

1. Step 1: Trace the swapping and insertion in arr2

   For each element in arr1, if it is greater than arr2[0], swap and then insert arr2[0] in sorted order in arr2. This pushes larger elements to arr2.

2. Step 2: Final arrays after all iterations

   After all swaps and insertions, arr1 becomes [1, 2, 3, 5, 8, 9] and arr2 becomes [10, 13, 15, 20].

3. Final Answer:

   arr1 = [1, 2, 3, 5, 8, 9], arr2 = [10, 13, 15, 20] -> Option D

4. Quick Check:

   In-place merge with insertion sort = arr1 and arr2 sorted [OK]

Hint: Swap if arr1[i] > arr2[0], then insert arr2[0] sorted [OK]

Common Mistakes:

• Not inserting arr2[0] correctly after swap
• Overwriting arr2 elements incorrectly
• Confusing array indices during insertion

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;
    int first = arr2[0];
    int k = 1;
    while (k < m && arr2[k] < first) {
      arr2[k - 1] = arr2[k];
      k++;
    }
    arr2[k] = first;
  }
}

medium

A. The insertion index in arr2 is incorrect; should be arr2[k - 1] = first

B. The swap logic between arr1[i] and arr2[0] is wrong

C. The loop should run from i = 1 instead of 0

D. The condition arr2[k] < first should be arr2[k] > first

Solution

1. Step 1: Analyze insertion logic in arr2

   The code shifts elements left to make space for 'first'. The correct insertion index after shifting is k - 1, not k.

2. Step 2: Identify the error impact

   Assigning arr2[k] = first overwrites the next element incorrectly, causing wrong order.

3. Final Answer:

   The insertion index in arr2 is incorrect; should be arr2[k - 1] = first -> Option A

4. Quick Check:

   Correct insertion index = k - 1 [OK]

Hint: Insert shifted element at k-1 index after loop ends [OK]

Common Mistakes:

• Using wrong index for insertion after shifting
• Incorrect swap logic
• Wrong loop start index

5. Given two sorted arrays:
arr1 = [1, 4, 7, 8, 10]
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 sorted elements? Choose the correct final arrays.

hard

A. arr1 = [1, 2, 3, 4, 7], arr2 = [8, 9, 10]

B. arr1 = [1, 3, 4, 7, 8], arr2 = [2, 9, 10]

C. arr1 = [1, 2, 4, 7, 8], arr2 = [3, 9, 10]

D. arr1 = [1, 2, 3, 4, 8], arr2 = [7, 9, 10]

Solution

1. Step 1: Compare and swap elements between arr1 and arr2

   Start from beginning of arr1, if arr1[i] > arr2[0], swap and then insert arr2[0] in sorted order in arr2.

2. Step 2: After all swaps and insertions

   arr1 becomes [1, 2, 3, 4, 7] and arr2 becomes [8, 9, 10], maintaining sorted order without extra space.

3. Final Answer:

   arr1 = [1, 2, 3, 4, 7], arr2 = [8, 9, 10] -> Option A

4. Quick Check:

   In-place merge keeps first array smallest elements [OK]

Hint: Swap if arr1[i] > arr2[0], then insert arr2[0] sorted [OK]

Common Mistakes:

• Not maintaining sorted order after swap
• Incorrect insertion in second array
• Assuming extra space is allowed