Merge Two Sorted Arrays Without Extra Space in DSA Javascript - 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 elements

↓

Sort B

↓

Repeat comparison until no swaps

↓

Done: Both arrays sorted and merged

We repeatedly compare the largest element of the first array with the smallest of the second. If out of order, we swap and then sort B. Repeat until no swaps are needed. Finally, sort A.

Execution Sample

DSA Javascript

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

This code merges two sorted arrays A and B without extra space by swapping and sorting the second array repeatedly and sorting the first array at the end.

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]	i=5	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]	i=5	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]	i=4	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]	i=4	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]	i=3	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]	i=3	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 needed
12	Compare A[1]=5 and B[0]=10	[1,5,9,8,3,2]	[10,13,15,20]	i=1	No swap needed
13	Compare A[0]=1 and B[0]=10	[1,5,9,8,3,2]	[10,13,15,20]	i=0	No swap needed
14	i < 0, loop ends, sort A	[1,2,3,5,8,9]	[10,13,15,20]	i=-1	A: 1->2->3->5->8->9 B: 10->13->15->20

💡 Loop ends when i < 0, A is sorted. Both arrays sorted and merged without extra space.

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]	[1,2,3,5,8,9]
B	[2,3,8,13]	[20,3,8,13]	[15,8,13,20]	[10,13,15,20]	[10,13,15,20]	[10,13,15,20]
i	5	5	4	3	2	-1

Key Moments - 3 Insights

Why do we sort array B after swapping elements?

Because after swapping, the first element of B might be larger than others, breaking B's sorted order. Sorting B restores its order, as shown in steps 3, 6, and 9.

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 element in A is at the end (A[i]) and the smallest in B is at the start (B[0]). Comparing these ensures correct order between arrays, as seen in step 1.

What stops the loop from running forever?

The loop runs from i = A.length - 1 down to 0. When i < 0, the loop ends (step 14). Also, swaps only happen if A[i] > B[0], so eventually no swaps occur and arrays are merged.

Visual Quiz - 3 Questions

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

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

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

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

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

💡 Hint

Check the 'A Array' column in row with Step 5 in execution_table.

At which step does the condition A[i] > B[0] become false for the first time?

A Step 10

B Step 11

C Step 12

D Step 13

💡 Hint

Look at the 'Operation' and 'Pointer Changes' columns around steps 10 and 11.

If we skip sorting B after swapping, what would happen?

A Array A becomes unsorted

B Arrays remain sorted correctly

C Array B becomes unsorted, breaking the merge logic

D No change in arrays

💡 Hint

Refer to key_moments about why sorting B is necessary after swaps.

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 for all elements in A from end to start
- Sort array A after the loop
- Result: Both arrays sorted without extra space

Full Transcript

This visualization shows how to merge two sorted arrays without 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. Then, we sort the second array to keep it sorted. We repeat this process moving backward through the first array until no swaps are needed. The execution table tracks each step, showing the arrays' states and pointer positions. Key moments clarify why sorting the second array after swapping is necessary and why we compare specific elements. The quiz tests understanding of array states and loop conditions. This method merges arrays efficiently without extra memory.

Practice

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

easy

A. Sort each array separately without merging

B. Create a new array to hold all elements from both arrays

C. Copy elements from one array to another without sorting

D. Combine both arrays into one sorted array without using extra memory

Solution

1. Step 1: Understand the problem requirement

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

2. Step 2: Identify the approach

   We must rearrange elements within the given arrays themselves to maintain sorted order combined.

3. Final Answer:

   Combine both arrays into one sorted array without using extra memory -> Option D

4. Quick Check:

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

Hint: Think in-place rearrangement, not new arrays [OK]

Common Mistakes:

• Assuming extra arrays are allowed
• Sorting arrays separately without merging
• Copying elements without sorting

2. Which of the following JavaScript syntax snippets correctly swaps two elements a[i] and b[j] without using a temporary variable?

easy

A. [a[i], b[j]] = [b[j], a[i]];

B. temp = a[i]; a[i] = b[j]; b[j] = temp;

C. a[i] = b[j]; b[j] = a[i];

D. a[i], b[j] = b[j], a[i];

Solution

1. Step 1: Identify correct swap syntax in JavaScript

   Using destructuring assignment, [a[i], b[j]] = [b[j], a[i]]; swaps values without a temporary variable.

2. Step 2: Check other options

   temp = a[i]; a[i] = b[j]; b[j] = temp; uses a temporary variable, C incorrectly assigns twice, D is invalid syntax.

3. Final Answer:

   [a[i], b[j]] = [b[j], a[i]]; -> Option A

4. Quick Check:

   Destructuring swap = [a[i], b[j]] = [b[j], a[i]]; [OK]

Hint: Use destructuring assignment for swap without temp [OK]

Common Mistakes:

• Using invalid syntax like option D
• Forgetting to use a temporary variable if not destructuring
• Assigning values incorrectly causing data loss

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

let a = [1, 5, 9, 10];
let b = [2, 3, 8, 13];

for (let i = 0; i < a.length; i++) {
  if (a[i] > b[0]) {
    [a[i], b[0]] = [b[0], a[i]];
    b.sort((x, y) => x - y);
  }
}

medium

A. a = [1, 2, 3, 5], b = [8, 9, 10, 13]

B. a = [1, 3, 5, 8], b = [2, 9, 10, 13]

C. a = [1, 2, 5, 8], b = [3, 9, 10, 13]

D. a = [1, 2, 3, 8], b = [5, 9, 10, 13]

Solution

1. Step 1: Trace the loop and swaps

   i=0: a[0]=1 <= b[0]=2 no swap
   i=1: a[1]=5 > b[0]=2 swap -> a[1]=2, b[0]=5; b sorted: [3,5,8,13]
   i=2: a[2]=9 > b[0]=3 swap -> a[2]=3, b[0]=9; b sorted: [5,8,9,13]
   i=3: a[3]=10 > b[0]=5 swap -> a[3]=5, b[0]=10; b sorted: [8,9,10,13]

2. Step 2: Final arrays after loop

   a = [1, 2, 3, 5]
   b = [8, 9, 10, 13]

3. Final Answer:

   a = [1, 2, 3, 5], b = [8, 9, 10, 13] -> Option A

4. Quick Check:

   Swapped and sorted b each time = a = [1, 2, 3, 5], b = [8, 9, 10, 13] [OK]

Hint: Swap if a[i] > b[0], then sort b [OK]

Common Mistakes:

• Not sorting array b after swap
• Swapping incorrectly causing wrong order
• Assuming arrays merge into one

4. Identify the error in this code snippet intended to merge two sorted arrays without extra space:

let a = [1, 4, 7];
let b = [2, 5, 6];

for (let i = 0; i < a.length; i++) {
  if (a[i] > b[0]) {
    let temp = a[i];
    a[i] = b[0];
    b[0] = temp;
  }
  b.sort();
}

medium

A. The if condition should be a[i] < b[0] instead of a[i] > b[0]

B. The sort() method is called without a compare function, causing incorrect sorting

C. Loop should run over array b length instead of a length

D. Swapping elements uses a temporary variable incorrectly

Solution

1. Step 1: Check the sorting method used

   The code uses b.sort() without a compare function, which sorts elements as strings, not numbers, causing wrong order.

2. Step 2: Correct sorting approach

   Use b.sort((x, y) => x - y) to sort numbers correctly.

3. Final Answer:

   The sort() method is called without a compare function, causing incorrect sorting -> Option B

4. Quick Check:

   sort() without compare = wrong numeric order [OK]

Hint: Always provide compare function for numeric sort [OK]

Common Mistakes:

• Using default sort() for numbers
• Swapping incorrectly without temp variable
• Wrong loop range

5. Given two sorted arrays a = [1, 3, 5, 7] and b = [0, 2, 6, 8, 9], how can you merge them without extra space so that after merging, a contains the first 4 smallest elements and b contains the remaining elements sorted? Which approach is best?

hard

A. Swap elements only if a[i] > b[j] without sorting b after swaps

B. Concatenate arrays and sort the combined array

C. Use a gap method to compare and swap elements between arrays until fully sorted

D. Copy all elements to a new array and then split back

Solution

1. Step 1: Understand the gap method

   The gap method compares elements at a certain gap distance in both arrays and swaps if needed, reducing the gap until 1, ensuring sorted order without extra space.

2. Step 2: Why other options fail

   Concatenate arrays and sort the combined array and D use extra space, violating constraints. Swap elements only if a[i] > b[j] without sorting b after swaps misses sorting after swaps, causing incorrect order.

3. Final Answer:

   Use a gap method to compare and swap elements between arrays until fully sorted -> Option C

4. Quick Check:

   Gap method = in-place merge without extra space [OK]

Hint: Use gap method to merge in-place efficiently [OK]

Common Mistakes:

• Using extra arrays violating constraints
• Not sorting after swaps causing disorder
• Assuming simple swaps suffice without gap reduction