Merge Two Sorted Arrays Without Extra Space in DSA Java - Execution Trace

Concept Flow - Merge Two Sorted Arrays Without Extra Space

Start with two sorted arrays A and B

↓

Compare last element of A with first element of B

↓

If A's last > B's first

↓

Swap A's last and B's first

↓

Sort array B to maintain order

↓

Repeat until no swaps needed

↓

Arrays merged without extra space

We repeatedly compare and swap elements between the two arrays to ensure all smaller elements are in the first array and larger in the second, sorting the second array after each swap.

Execution Sample

DSA Java

import java.util.Arrays;

int[] A = {1, 5, 9, 10, 15, 20};
int[] B = {2, 3, 8, 13};
// Merge without extra space
for (int i = A.length - 1; i >= 0; i--) {
  if (A[i] > B[0]) {
    int temp = A[i]; A[i] = B[0]; B[0] = temp;
    Arrays.sort(B);
  }
}

This code merges two sorted arrays A and B without extra space by swapping and sorting.

Execution Table

Step	Operation	A Array	B Array	Pointer Changes	Visual State
1	Compare A[5]=20 and B[0]=2	[1,5,9,10,15,20]	[2,3,8,13]	i=5	A:1->5->9->10->15->20, B:2->3->8->13
2	20 > 2, swap A[5] and B[0]	[1,5,9,10,15,2]	[20,3,8,13]	Swap A[5]<->B[0]	A:1->5->9->10->15->2, B:20->3->8->13
3	Sort B	[1,5,9,10,15,2]	[3,8,13,20]	B sorted	A:1->5->9->10->15->2, B:3->8->13->20
4	Compare A[4]=15 and B[0]=3	[1,5,9,10,15,2]	[3,8,13,20]	i=4	A:1->5->9->10->15->2, B:3->8->13->20
5	15 > 3, swap A[4] and B[0]	[1,5,9,10,3,2]	[15,8,13,20]	Swap A[4]<->B[0]	A:1->5->9->10->3->2, B:15->8->13->20
6	Sort B	[1,5,9,10,3,2]	[8,13,15,20]	B sorted	A:1->5->9->10->3->2, B:8->13->15->20
7	Compare A[3]=10 and B[0]=8	[1,5,9,10,3,2]	[8,13,15,20]	i=3	A:1->5->9->10->3->2, B:8->13->15->20
8	10 > 8, swap A[3] and B[0]	[1,5,9,8,3,2]	[10,13,15,20]	Swap A[3]<->B[0]	A:1->5->9->8->3->2, B:10->13->15->20
9	Sort B	[1,5,9,8,3,2]	[10,13,15,20]	B sorted	A:1->5->9->8->3->2, B:10->13->15->20
10	Compare A[2]=9 and B[0]=10	[1,5,9,8,3,2]	[10,13,15,20]	i=2	A:1->5->9->8->3->2, B:10->13->15->20
11	9 > 10? No	[1,5,9,8,3,2]	[10,13,15,20]	i=2, no swap	A:1->5->9->8->3->2, B:10->13->15->20

💡 At step 11, A[2]=9 is not greater than B[0]=10, so no swap needed; merging complete.

Variable Tracker

Variable	Start	After Step 2	After Step 5	After Step 8	After Step 11 (Final)
A	[1,5,9,10,15,20]	[1,5,9,10,15,2]	[1,5,9,10,3,2]	[1,5,9,8,3,2]	[1,5,9,8,3,2]
B	[2,3,8,13]	[20,3,8,13]	[15,8,13,20]	[10,13,15,20]	[10,13,15,20]
i	5	4	3	2	2

Key Moments - 3 Insights

Why do we sort array B after swapping elements?

After swapping, B's first element may be larger than others, breaking its sorted order. Sorting B (see steps 3, 6, 9) restores order so comparisons remain valid.

Why do we compare A[i] with B[0] instead of other elements?

Because A is sorted ascending and B is sorted ascending, the largest elements in A are at the end, and the smallest in B are at the start. Comparing A[i] with B[0] ensures we only swap when needed to maintain global order (see steps 1, 4, 7, 10).

Why does the loop stop when A[i] <= B[0]?

When A[i] is not greater than B[0], it means all elements in A are smaller or equal to B's smallest, so arrays are merged correctly (step 11). No further swaps needed.

Visual Quiz - 3 Questions

Look at the execution table, what is the state of array A after step 5?

A [1,5,9,8,3,2]

B [1,5,9,10,3,2]

C [1,5,9,10,15,2]

D [1,5,9,10,15,20]

💡 Hint

Check the 'A Array' column at step 5 in the execution_table.

At which step does the condition A[i] > B[0] become false, stopping the loop?

A Step 9

B Step 11

C Step 8

D Step 6

💡 Hint

Look at the 'Operation' and 'Pointer Changes' columns in the execution_table for the stopping condition.

If we did not sort array B after swapping, what would happen to the merging process?

A Array B would become unsorted, causing incorrect comparisons.

B The arrays would still merge correctly.

C Array A would become unsorted.

D The loop would run infinitely.

💡 Hint

Refer to the 'Operation' column where sorting B is done after swaps (steps 3, 6, 9).

Concept Snapshot

Merge Two Sorted Arrays Without Extra Space:
- Compare last element of A with first of B
- If A[i] > B[0], swap them
- Sort array B after swap
- Repeat until no swaps needed
- Result: two sorted arrays merged without extra space

Full Transcript

This concept shows how to merge two sorted arrays without using extra space. We start by comparing the last element of the first array with the first element of the second array. If the element in the first array is bigger, we swap it with the smaller element in the second array. After swapping, we sort the second array to keep it sorted. We repeat this process moving backward through the first array until no more swaps are needed. This way, all smaller elements end up in the first array and larger ones in the second, achieving a merged sorted state without extra memory.

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