Merge Two Sorted Arrays Without Extra Space in DSA C - Practice Problems & Challenges

Challenge - 5 Problems

❓ Predict Output

intermediate

Output of merging two sorted arrays without extra space

What is the output of the following code after merging two sorted arrays without using extra space?

DSA C

void merge(int arr1[], int arr2[], int n, int m) {
    int i = 0, j = 0, k = n - 1;
    while (i <= k && j < m) {
        if (arr1[i] < arr2[j]) {
            i++;
        } else {
            int temp = arr2[j];
            arr2[j] = arr1[k];
            arr1[k] = temp;
            j++;
            k--;
        }
    }
    // Sort both arrays
    for (int x = 0; x < n - 1; x++) {
        for (int y = 0; y < n - x - 1; y++) {
            if (arr1[y] > arr1[y + 1]) {
                int temp = arr1[y];
                arr1[y] = arr1[y + 1];
                arr1[y + 1] = temp;
            }
        }
    }
    for (int x = 0; x < m - 1; x++) {
        for (int y = 0; y < m - x - 1; y++) {
            if (arr2[y] > arr2[y + 1]) {
                int temp = arr2[y];
                arr2[y] = arr2[y + 1];
                arr2[y + 1] = temp;
            }
        }
    }
}

int main() {
    int arr1[5] = {1, 5, 9, 10, 15};
    int arr2[4] = {2, 3, 8, 13};
    merge(arr1, arr2, 5, 4);
    // Print arr1
    for (int i = 0; i < 5; i++) {
        printf("%d ", arr1[i]);
    }
    printf("\n");
    // Print arr2
    for (int i = 0; i < 4; i++) {
        printf("%d ", arr2[i]);
    }
    return 0;
}

A 1 2 3 5 8 \n 9 10 13 15 \n

B 1 2 3 8 9 \n 5 10 13 15 \n

C 1 3 5 8 9 \n 2 10 13 15 \n

D 1 2 3 5 9 \n 8 10 13 15 \n

💡 Hint

Focus on swapping larger elements from arr1 with smaller elements from arr2, then sorting both arrays.

The code swaps elements between arr1 and arr2 to ensure all smaller elements are in arr1 and larger in arr2, then sorts both arrays. The final arrays are arr1: [1, 2, 3, 5, 8] and arr2: [9, 10, 13, 15].

🧠 Conceptual

intermediate

Understanding the in-place merge approach

Why does the algorithm swap elements between the end of the first array and the beginning of the second array during merging without extra space?

A To reverse both arrays before merging them.

B To move larger elements to the second array and smaller elements to the first array for easier sorting later.

C To create a new array inside the function for merging.

D To sort the arrays individually before merging.

💡 Hint

Think about how to keep the smallest elements in the first array without extra space.

Swapping ensures that smaller elements end up in the first array and larger ones in the second, so sorting them individually afterward results in fully merged sorted arrays without extra space.

🔧 Debug

advanced

Identify the error in this merge function

What error will the following code produce when merging two sorted arrays without extra space?

DSA C

void merge(int arr1[], int arr2[], int n, int m) {
    int i = 0, j = 0, k = n - 1;
    while (i < k && j < m) {
        if (arr1[i] < arr2[j]) {
            i++;
        } else {
            int temp = arr2[j];
            arr2[j] = arr1[k];
            arr1[k] = temp;
            j++;
            k--;
        }
    }
    // Sorting code omitted for brevity
}

A Compilation error due to missing semicolon.

B Array index out of bounds when k becomes negative.

C No error; code runs correctly.

D Infinite loop because condition i < k excludes i == k causing missed swaps.

💡 Hint

Check the loop condition carefully and consider when i equals k.

The loop condition i < k misses the case when i == k, so the last element might not be swapped if needed, potentially causing the loop to never terminate if elements are not in order.

❓ Predict Output

advanced

Output after merging arrays with duplicates

What is the output of the following code after merging two sorted arrays with duplicates without extra space?

DSA C

void merge(int arr1[], int arr2[], int n, int m) {
    int i = 0, j = 0, k = n - 1;
    while (i <= k && j < m) {
        if (arr1[i] <= arr2[j]) {
            i++;
        } else {
            int temp = arr2[j];
            arr2[j] = arr1[k];
            arr1[k] = temp;
            j++;
            k--;
        }
    }
    // Sort both arrays
    for (int x = 0; x < n - 1; x++) {
        for (int y = 0; y < n - x - 1; y++) {
            if (arr1[y] > arr1[y + 1]) {
                int temp = arr1[y];
                arr1[y] = arr1[y + 1];
                arr1[y + 1] = temp;
            }
        }
    }
    for (int x = 0; x < m - 1; x++) {
        for (int y = 0; y < m - x - 1; y++) {
            if (arr2[y] > arr2[y + 1]) {
                int temp = arr2[y];
                arr2[y] = arr2[y + 1];
                arr2[y + 1] = temp;
            }
        }
    }
}

int main() {
    int arr1[6] = {1, 3, 5, 7, 7, 9};
    int arr2[5] = {2, 3, 7, 8, 10};
    merge(arr1, arr2, 6, 5);
    for (int i = 0; i < 6; i++) {
        printf("%d ", arr1[i]);
    }
    printf("\n");
    for (int i = 0; i < 5; i++) {
        printf("%d ", arr2[i]);
    }
    return 0;
}

A 1 3 3 5 7 7 \n 2 7 8 9 10 \n

B 1 2 3 5 7 7 \n 3 7 8 9 10 \n

C 1 2 3 3 5 7 \n 7 7 8 9 10 \n

D 1 2 3 5 7 9 \n 3 7 7 8 10 \n

💡 Hint

Duplicates are handled by swapping and sorting; check how equal elements are compared.

The code swaps elements to ensure smaller or equal elements stay in arr1, then sorts both arrays. The final arrays are arr1: [1, 2, 3, 3, 5, 7] and arr2: [7, 7, 8, 9, 10].

🚀 Application

expert

Minimum number of swaps to merge two sorted arrays without extra space

Given two sorted arrays arr1 and arr2, what is the minimum number of swaps performed by the in-place merge algorithm to merge them without extra space?

DSA C

void merge(int arr1[], int arr2[], int n, int m) {
    int i = 0, j = 0, k = n - 1;
    int swap_count = 0;
    while (i <= k && j < m) {
        if (arr1[i] <= arr2[j]) {
            i++;
        } else {
            int temp = arr2[j];
            arr2[j] = arr1[k];
            arr1[k] = temp;
            j++;
            k--;
            swap_count++;
        }
    }
    // Sorting code omitted
    printf("Swaps: %d\n", swap_count);
}

int main() {
    int arr1[5] = {1, 4, 7, 8, 10};
    int arr2[4] = {2, 3, 9, 15};
    merge(arr1, arr2, 5, 4);
    return 0;
}

A 2

B 3

C 1

D 4

💡 Hint

Count how many times elements from arr2 are smaller than elements at the end of arr1.

The swaps happen when arr2[j] < arr1[k]. Here, arr2[0]=2 < arr1[4]=10 (swap 1), arr2[1]=3 < arr1[3]=8 (swap 2), arr2[2]=9 < arr1[2]=7 (no swap), so total swaps = 2.