Merge Two Sorted Arrays Without Extra Space in DSA Python - Build from Scratch

Merge Two Sorted Arrays Without Extra Space

📖 Scenario: You work in a warehouse where two separate shelves hold sorted boxes by size. You want to combine these boxes into one sorted sequence without using extra space, so you can organize them efficiently without needing a new shelf.

🎯 Goal: Build a program that merges two sorted arrays into one sorted sequence without using extra space. The first array should contain the smallest elements and the second array the remaining larger elements after merging.

📋 What You'll Learn

Create two sorted arrays with exact values

Use a variable to track the length of the first array

Implement the merge logic without extra space

Print the two arrays after merging

💡 Why This Matters

🌍 Real World

Merging sorted data streams or lists efficiently without extra memory is useful in embedded systems or memory-limited environments.

💼 Career

This technique is important for software engineers working with low-level data processing, optimizing memory usage, or working on performance-critical applications.

1

Create two sorted arrays

Create two sorted arrays called arr1 and arr2 with these exact values: arr1 = [1, 5, 9, 10, 15, 20] and arr2 = [2, 3, 8, 13]

DSA Python

# Create two sorted arrays arr1 and arr2 with given values
# Your code here

Hint

Use square brackets to create lists and assign the exact values to arr1 and arr2.

2

Set the length of the first array

Create a variable called n and set it to the length of arr1 using the len() function

DSA Python

arr1 = [1, 5, 9, 10, 15, 20]
arr2 = [2, 3, 8, 13]
# Create variable n as length of arr1
# Your code here

Hint

Use len(arr1) to get the number of elements in arr1.

3

Merge the two arrays without extra space

Use a for loop with variable i from 0 to n - 1 to compare elements of arr1 and arr2. If arr1[i] is greater than arr2[0], swap them and then sort arr2 to keep it sorted

DSA Python

arr1 = [1, 5, 9, 10, 15, 20]
arr2 = [2, 3, 8, 13]
n = len(arr1)
# Merge arr1 and arr2 without extra space
# Your code here

Hint

Loop through arr1 and swap elements with the first element of arr2 if needed, then sort arr2 to keep it sorted.

4

Print the merged arrays

Print arr1 and arr2 on separate lines using two print() statements

DSA Python

arr1 = [1, 5, 9, 10, 15, 20]
arr2 = [2, 3, 8, 13]
n = len(arr1)

for i in range(n):
    if arr1[i] > arr2[0]:
        arr1[i], arr2[0] = arr2[0], arr1[i]
        arr2.sort()

# Print arr1 and arr2
# Your code here

Hint

Use print(arr1) and print(arr2) to display the final arrays.