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

Yes→Swap elements

↓

Sort array B

↓

Sort array A

↓

Repeat until no swaps

↓

Merged arrays

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 each after swaps until fully merged without extra space.

Execution Sample

DSA Python

A = [1, 5, 9, 10, 15, 20]
B = [2, 3, 8, 13]
i = len(A) - 1
j = 0
while i >= 0 and j < len(B):
    if A[i] > B[j]:
        A[i], B[j] = B[j], A[i]
    i -= 1
    j += 1
A.sort()
B.sort()

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

Execution Table

Step	Operation	i	j	A Array	B Array	Swap Happened	Notes
1	Compare A[5]=20 and B[0]=2	5	0	[1, 5, 9, 10, 15, 20]	[2, 3, 8, 13]	Yes	20 > 2, swap A[5] and B[0]
2	After swap	5	0	[1, 5, 9, 10, 15, 2]	[20, 3, 8, 13]	N/A	Arrays updated
3	Decrement i, increment j	4	1	[1, 5, 9, 10, 15, 2]	[20, 3, 8, 13]	N/A	Prepare next comparison
4	Compare A[4]=15 and B[1]=3	4	1	[1, 5, 9, 10, 15, 2]	[20, 3, 8, 13]	Yes	15 > 3, swap A[4] and B[1]
5	After swap	4	1	[1, 5, 9, 10, 3, 2]	[20, 15, 8, 13]	N/A	Arrays updated
6	Decrement i, increment j	3	2	[1, 5, 9, 10, 3, 2]	[20, 15, 8, 13]	N/A	Prepare next comparison
7	Compare A[3]=10 and B[2]=8	3	2	[1, 5, 9, 10, 3, 2]	[20, 15, 8, 13]	Yes	10 > 8, swap A[3] and B[2]
8	After swap	3	2	[1, 5, 9, 8, 3, 2]	[20, 15, 10, 13]	N/A	Arrays updated
9	Decrement i, increment j	2	3	[1, 5, 9, 8, 3, 2]	[20, 15, 10, 13]	N/A	Prepare next comparison
10	Compare A[2]=9 and B[3]=13	2	3	[1, 5, 9, 8, 3, 2]	[20, 15, 10, 13]	No	9 <= 13, no swap
11	Decrement i, increment j	1	4	[1, 5, 9, 8, 3, 2]	[20, 15, 10, 13]	N/A	j out of range, stop loop
12	Sort A	-	-	[1, 2, 3, 5, 8, 9]	[20, 15, 10, 13]	N/A	Sort first array
13	Sort B	-	-	[1, 2, 3, 5, 8, 9]	[10, 13, 15, 20]	N/A	Sort second array
14	Final merged arrays	-	-	[1, 2, 3, 5, 8, 9]	[10, 13, 15, 20]	N/A	Arrays merged without extra space

💡 Loop ends when j reaches length of B (4), no more elements to compare.

Variable Tracker

Variable	Start	After Step 1	After Step 4	After Step 7	After Step 10	Final
i	5	5	4	3	2	1
j	0	0	1	2	3	4
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]	[20,15,8,13]	[20,15,10,13]	[20,15,10,13]	[10,13,15,20]

Key Moments - 3 Insights

Why do we compare A's last element with B's first element?

Because A and B are sorted, the largest element in A is at the end and the smallest in B is at the start. Swapping these ensures smaller elements move to A and larger to B, as shown in steps 1 and 4.

Why do we sort arrays after swapping instead of during?

Sorting after all swaps is efficient because swapping only moves some elements out of order. Sorting at the end (steps 12 and 13) restores order without extra space.

What stops the swapping loop?

The loop stops when j reaches the length of B (step 11), meaning all elements in B have been compared and swapped if needed.

Visual Quiz - 3 Questions

Look at the execution table at step 4, what are the contents of arrays A and B?

A A = [1, 5, 9, 10, 3, 2], B = [20, 15, 8, 13]

B A = [1, 5, 9, 10, 15, 2], B = [20, 3, 8, 13]

C A = [1, 5, 9, 10, 15, 20], B = [2, 3, 8, 13]

D A = [1, 5, 9, 8, 3, 2], B = [20, 15, 10, 13]

💡 Hint

Check the 'After swap' row after step 1 in the execution_table.

At which step does the loop stop because j reaches the length of B?

A Step 10

B Step 12

C Step 11

D Step 13

💡 Hint

Look at the 'Notes' column in the execution_table for the step where j goes out of range.

If we did not sort arrays after swapping, what would be the state of array A at the end of swaps?

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

B [20, 15, 10, 13]

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

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

💡 Hint

Check the array A state at step 10 before sorting in the execution_table.

Concept Snapshot

Merge Two Sorted Arrays Without Extra Space:
- Compare last of A with first of B
- Swap if A's element is bigger
- Move pointers i (end of A) and j (start of B)
- Repeat until no swaps possible
- Sort both arrays at the end
- Result: merged arrays 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 them. We then move the pointers inward and repeat this process. After all swaps, we sort both arrays to restore order. This way, all smaller elements end up in the first array and larger ones in the second, achieving a merged result without extra memory. The execution table traces each step, showing swaps and array states. Key moments clarify why we compare these elements and why sorting is done after swapping. The visual quiz tests understanding of array states and loop termination.