Merge Two Sorted Arrays Without Extra Space in DSA Java

Mental Model

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

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

Array1: [1] -> [5] -> [9] -> null
Array2: [2] -> [6] -> [8] -> null

Dry Run Walkthrough

Input: array1: [1, 5, 9], array2: [2, 6, 8]

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

Step 1: Compare last element of array1 (9) with first element of array2 (2), since 9 > 2, swap them

array1: [1, 5, 2]
array2: [9, 6, 8]

Why: To ensure smaller elements stay in array1 and larger in array2

Step 2: Sort array2 to restore order: [6, 8, 9]

array1: [1, 5, 2]
array2: [6, 8, 9]

Why: Sorting array2 after swap keeps it sorted

Step 3: Sort array1 to restore order: [1, 2, 5]

array1: [1, 2, 5]
array2: [6, 8, 9]

Why: Sorting array1 after swap keeps it sorted

Step 4: Compare last element of array1 (5) with first element of array2 (6), since 5 <= 6, stop

array1: [1, 2, 5]
array2: [6, 8, 9]

Why: Arrays are now merged in sorted order without extra space

Result:

array1: [1, 2, 5]
array2: [6, 8, 9]

Annotated Code

DSA Java

import java.util.Arrays;

public class MergeSortedArrays {

    public static void mergeWithoutExtraSpace(int[] arr1, int[] arr2) {
        int n = arr1.length;
        int m = arr2.length;

        for (int i = n - 1; i >= 0; i--) {
            if (arr1[i] > arr2[0]) {
                // Swap arr1[i] and arr2[0]
                int temp = arr1[i];
                arr1[i] = arr2[0];
                arr2[0] = temp;

                // After swap, sort arr2 to keep it sorted
                int first = arr2[0];
                int k;
                for (k = 1; k < m && arr2[k] < first; k++) {
                    arr2[k - 1] = arr2[k];
                }
                arr2[k - 1] = first;
            }
        }
    }

    public static void main(String[] args) {
        int[] array1 = {1, 5, 9};
        int[] array2 = {2, 6, 8};

        mergeWithoutExtraSpace(array1, array2);

        System.out.println("array1: " + Arrays.toString(array1));
        System.out.println("array2: " + Arrays.toString(array2));
    }
}

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

iterate backward through arr1 to compare largest elements

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 bigger element to arr2 and smaller to arr1

int first = arr2[0]; int k; for (k = 1; k < m && arr2[k] < first; k++) { arr2[k - 1] = arr2[k]; } arr2[k - 1] = first;

insertion sort step to place swapped element in correct position in arr2

Output

array1: [1, 2, 5]

array2: [6, 8, 9]

Complexity Analysis

Time: O(n*m) because for each element in arr1 we may shift elements in arr2 to keep it sorted

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

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

No swaps needed, arrays remain as is

DSA Java

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

All elements in arr1 smaller than arr2

No swaps occur, arrays remain sorted

DSA Java

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

All elements in arr1 larger than arr2

Multiple swaps and shifts happen to reorder arrays

DSA Java

int first = arr2[0]; int k; for (k = 1; k < m && arr2[k] < first; k++) { arr2[k - 1] = arr2[k]; } arr2[k - 1] = first;

When to Use This Pattern

When asked to merge two sorted arrays without extra space, use the swapping and insertion approach to reorder elements in place efficiently.

Common Mistakes

Mistake: Trying to merge by simply concatenating arrays without sorting or swapping
Fix: Implement the swap and insertion logic to maintain sorted order without extra space

Mistake: Sorting entire arrays after each swap causing high time complexity
Fix: Use insertion logic only on arr2 after swap to keep it sorted efficiently

Summary

Merges two sorted arrays into sorted order without using extra space by swapping and inserting elements.

Use when memory is limited and you must merge two sorted arrays in place.

The key insight is swapping the bigger element from the first array with the smaller element from the second, then inserting it correctly.

Practice

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

easy

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

B. Copy all elements into a new array and sort it

C. Sort each array separately without merging

D. Use a temporary array to hold merged elements

Solution

1. Step 1: Understand the problem requirement

   The problem asks to merge two sorted arrays into a sorted sequence without using extra space, meaning no additional arrays or large memory allocation.

2. Step 2: Identify the correct approach

   Using in-place techniques like swapping elements between arrays and sorting them ensures no extra space is used.

3. Final Answer:

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

4. Quick Check:

   Merge without extra space = Combine in-place [OK]

Hint: Remember: no extra array means in-place merging [OK]

Common Mistakes:

• Thinking extra array is allowed
• Sorting arrays separately without merging
• Using extra memory for temporary storage

2. Which of the following Java code snippets correctly swaps elements between two arrays arr1 and arr2 at indices i and j without extra space?

easy

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

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

C. int temp = arr2[j]; arr1[i] = arr2[j]; arr2[j] = temp;

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

Solution

1. Step 1: Check the swap logic

   Swapping requires a temporary variable to hold one value while assigning the other to avoid overwriting.

2. Step 2: Verify correct use of temp variable

   int temp = arr1[i]; arr1[i] = arr2[j]; arr2[j] = temp; uses a temp variable to hold arr1[i], then assigns arr2[j] to arr1[i], and finally assigns temp to arr2[j], correctly swapping values.

3. Final Answer:

   int temp = arr1[i]; arr1[i] = arr2[j]; arr2[j] = temp; -> Option D

4. Quick Check:

   Swap needs temp variable = int temp = arr1[i]; arr1[i] = arr2[j]; arr2[j] = temp; [OK]

Hint: Always use a temp variable to swap two values safely [OK]

Common Mistakes:

• Assigning without temp causes overwriting
• Swapping elements within the same array incorrectly
• Confusing indices during swap

3. Given two sorted arrays arr1 = [1, 5, 9, 10] and arr2 = [2, 3, 8, 13], after applying the merge without extra space algorithm, what will be the final state of arr1 and arr2?

medium

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

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

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

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

Solution

1. Step 1: Compare and swap elements between arrays

   Start comparing last element of arr1 with first of arr2. Swap if arr1 element is greater. After swaps, sort both arrays.

2. Step 2: Final sorted arrays after merging

   After swapping and sorting, 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 B

4. Quick Check:

   In-place merge sorts arrays = arr1 = [1, 2, 3, 5], arr2 = [8, 9, 10, 13] [OK]

Hint: Swap bigger arr1 elements with smaller arr2, then sort both [OK]

Common Mistakes:

• Not sorting arrays after swapping
• Swapping incorrectly leading to unsorted arrays
• Mixing indices during swaps

4. Identify the error in the following code snippet for merging two sorted arrays without extra space:

for (int i = 0; i < arr1.length; i++) {
  if (arr1[i] > arr2[0]) {
    int temp = arr1[i];
    arr1[i] = arr2[0];
    arr2[0] = temp;
    Arrays.sort(arr2);
  }
}

medium

A. Using Arrays.sort on arr1 instead of arr2 is required

B. Swapping elements without checking arr2 length causes error

C. Sorting arr2 inside the loop causes unnecessary repeated sorting

D. Loop should run until arr2.length instead of arr1.length

Solution

1. Step 1: Analyze sorting inside the loop

   The code sorts arr2 inside the loop every time a swap happens, which is inefficient and slows down the algorithm.

2. Step 2: Suggest optimization

   Sorting arr2 once after all swaps or using a better approach like gap method improves performance.

3. Final Answer:

   Sorting arr2 inside the loop causes unnecessary repeated sorting -> Option C

4. Quick Check:

   Repeated sorting inside loop = inefficiency [OK]

Hint: Avoid sorting inside loops; sort once after swaps [OK]

Common Mistakes:

• Sorting arr2 repeatedly inside loop
• Confusing loop limits between arrays
• Ignoring performance impact of repeated sorting

5. You have two sorted arrays arr1 = [1, 4, 7, 8, 10] and arr2 = [2, 3, 9]. Using the gap method to merge without extra space, what is the final state of both arrays?

hard

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

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

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

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

Solution

1. Step 1: Calculate initial gap and compare elements

   Total length is 8, initial gap = ceil(8/2) = 4. Compare elements at gap distance and swap if needed, then reduce gap.

2. Step 2: Perform gap reductions and swaps

   After successive gap reductions (4, 2, 1), arrays become sorted as arr1 = [1, 2, 3, 4, 7] and arr2 = [8, 9, 10].

3. Final Answer:

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

4. Quick Check:

   Gap method sorts arrays in-place = arr1 = [1, 2, 3, 4, 7], arr2 = [8, 9, 10] [OK]

Hint: Use gap method: reduce gap, swap if needed, repeat until gap=0 [OK]

Common Mistakes:

• Not reducing gap correctly
• Swapping wrong elements across arrays
• Confusing gap calculation with array lengths