Program to Merge One Sorted Array into Another Sorted Array

• Write a program to merge to sorted array into one single sorted array.

Given two sorted integer array. Size of first array is (M + N) but only first M locations are populated remaining are empty. Second array is of size equal to N. We have to merge these two sorted arrays into first array(bigger array) such that resultant array is also sorted.
For Example :
First Input Array : 1 3 5 7 9 11
Second Input Array : 2 4 6 8 10

Merged Array : 1 2 3 4 5 6 7 8 9 10 11

---

Algorithm to merge a sorted array of size N into another sorted array of size M + N
Let arrayOne and arrayTwo be two sorted arrays of length N and M + N.

• This approach is similar to the merge step of merge sort.
• Initialize two integer variable arrayOneIndex and arrayTwoIndex to index of last element of arrayOne and arrayTwo respectively. Also initialize mergedArrayIndex to last index of bigger array(arrayTwo).
• Now, compare the elements at both array at index arrayOneIndex and arrayTwoIndex and move the larger one to mergedArrayIndex location and decrement indexes accordingly.
• Continue moving larger element until any one array becomes empty. Then copy all the remaining elements of another array to merges array.
• Here we are populating merged array from back size. Largest numbers first.

Time Complexity : O(M + N)

---

C program to merge to sorted array

#include <stdio.h>

void mergeArrays(int *bigArray, int bigArrayCount, int *smallArray, int smallArrayCount){
    /* Input Validation */
    if(bigArray == NULL || smallArray == NULL)
        return;
     
    /* Initialize bigArrayIndex and smallArrayIndex to last 
    element of bigArray and smallArray respoctively. Set 
    mergedArrayIndex to the last index of merged array */
    int bigArrayIndex = bigArrayCount-1, 
    smallArrayIndex = smallArrayCount-1, 
    mergedArrayIndex = bigArrayCount + smallArrayCount -1;
    
    /* This step is similar ro merge step of merge sort. 
    Instead of merging smallest element first here we 
    are merging largest elements first */ 
    while(bigArrayIndex >= 0 && smallArrayIndex >= 0) {
 if(bigArray[bigArrayIndex] >= smallArray[smallArrayIndex]){
            bigArray[mergedArrayIndex] = bigArray[bigArrayIndex];
            mergedArrayIndex--;
            bigArrayIndex--;
        } else {
            bigArray[mergedArrayIndex] = smallArray[smallArrayIndex];
            mergedArrayIndex--;
            smallArrayIndex--;
        }
    }
    /* If bigArray end first then copy all remaining elements
    of smallArray to merged array */
    if(bigArrayIndex < 0){
        while(smallArrayIndex >= 0) {
            bigArray[mergedArrayIndex] = smallArray[smallArrayIndex];
            mergedArrayIndex--;
            smallArrayIndex--;
  }    
    } else if (smallArrayIndex < 0) {
    /* If smallArray end first then copy all remaining elements
    of bigArray to merged array */
        while(bigArrayIndex >= 0) {
            bigArray[mergedArrayIndex] = bigArray[bigArrayIndex];
            mergedArrayIndex--;
            bigArrayIndex--;
        }
    }
}

int main(){
    /* Big array of size 11, but only first 6 
    array indexes are filled remaining are empty */ 
    int bigArray[11] = {1, 3, 5, 7, 9, 11}; 
    int smallArray[5] = {2, 4, 6, 8, 10}; 
    int i;
 
    mergeArrays(bigArray, 6, smallArray, 5);
 
    printf("Merged Array\n");
    for(i = 0; i<11; i++){
 printf("%d ", bigArray[i]);
    }

    return 0;
}

Output

Merged Array
1 2 3 4 5 6 7 8 9 10 11