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

Merge Two Sorted Arrays Without Extra Space

📖 Scenario: You have two sorted arrays representing two shelves of books arranged by height. You want to merge these two shelves into one sorted arrangement without using extra space, so you can organize the books efficiently without needing a new shelf.

🎯 Goal: Write a program to merge two sorted arrays arr1 and arr2 into a single sorted sequence without using extra space. The final sorted elements should be distributed between arr1 and arr2.

📋 What You'll Learn

Create two sorted arrays arr1 and arr2 with given values

Create variables to hold the sizes of arr1 and arr2

Implement the merge logic without using extra space

Print the final merged arrays

💡 Why This Matters

🌍 Real World

Merging sorted lists without extra space is useful in memory-limited devices or when working with large datasets where extra memory allocation is costly.

💼 Career

Understanding in-place merging techniques is valuable for software engineers working on embedded systems, database engines, or performance-critical applications.

1

Create two sorted arrays

Create two sorted arrays called arr1 and arr2 with these exact values: arr1 contains 1, 5, 9, 10, 15, 20 and arr2 contains 2, 3, 8, 13. Also create integer variables n and m to store the sizes of arr1 and arr2 respectively.

DSA C

# Your code here

Hint

Use array initialization syntax and assign sizes to n and m.

2

Set up index variables for merging

Create three integer variables called i, j, and k. Initialize i to n - 1, j to 0, and k to 0. These will help in merging the arrays without extra space.

DSA C

int arr1[] = {1, 5, 9, 10, 15, 20};
int arr2[] = {2, 3, 8, 13};
int n = 6;
int m = 4;
// Your code here

Hint

Initialize i to the last index of arr1, j to the first index of arr2, and k to zero.

3

Merge arrays without extra space

Use a while loop with the condition i >= 0 && j < m. Inside the loop, compare arr1[i] and arr2[j]. If arr1[i] is greater, swap arr1[i] and arr2[j]. Then decrement i and increment j. After the loop, sort both arrays using a simple sorting method like bubble sort.

DSA C

int arr1[] = {1, 5, 9, 10, 15, 20};
int arr2[] = {2, 3, 8, 13};
int n = 6;
int m = 4;
int i = n - 1;
int j = 0;
int k = 0;
// Your code here

Hint

Swap elements when arr1[i] is bigger, then sort both arrays to finalize the merge.

4

Print the merged arrays

Use two for loops to print the elements of arr1 and arr2 separated by spaces. Print arr1 elements first, then print a newline, then print arr2 elements.

DSA C

int arr1[] = {1, 5, 9, 10, 15, 20};
int arr2[] = {2, 3, 8, 13};
int n = 6;
int m = 4;
int i = n - 1;
int j = 0;
int k = 0;

while (i >= 0 && j  arr2[j]) {
        int temp = arr1[i];
        arr1[i] = arr2[j];
        arr2[j] = temp;
    }
    i--;
    j++;
}

// Bubble sort for arr1
for (int x = 0; x  arr1[y + 1]) {
            int temp = arr1[y];
            arr1[y] = arr1[y + 1];
            arr1[y + 1] = temp;
        }
    }
}

// Bubble sort for arr2
for (int x = 0; x  arr2[y + 1]) {
            int temp = arr2[y];
            arr2[y] = arr2[y + 1];
            arr2[y + 1] = temp;
        }
    }
}
// Your code here

Hint

Print all elements of arr1 separated by spaces, then a newline, then all elements of arr2.