Merge an array of size n into another array of size m+n

Last Updated : 13 Jul, 2023

There are two sorted arrays. First one is of size m+n containing only m elements. Another one is of size n and contains n elements. Merge these two arrays into the first array of size m+n such that the output is sorted.
Input: array with m+n elements (mPlusN[]).

NA => Value is not filled/available in array mPlusN[]. There should be n such array blocks.
Input: array with n elements (N[]).

Output: N[] merged into mPlusN[] (Modified mPlusN[])

Algorithm:

Let first array be mPlusN[] and other array be N[] 1) Move m elements of mPlusN[] to end. 2) Start from nth element of mPlusN[] and 0th element of N[] and merge them into mPlusN[].

Below is the implementation of the above algorithm :

C++

// C++ program to Merge an array of  // size n into another array of size m + n #include <bits/stdc++.h> using namespace std; /* Assuming -1 is filled for the places  where element is not available */ #define NA -1 /* Function to move m elements at   the end of array mPlusN[] */ void moveToEnd(int mPlusN[], int size) {  int j = size - 1;  for (int i = size - 1; i >= 0; i--)  if (mPlusN[i] != NA)  {  mPlusN[j] = mPlusN[i];  j--;  } } /* Merges array N[] of size n into  array mPlusN[] of size m+n*/ void merge(int mPlusN[], int N[], int m, int n) {  int i = n; /* Current index of i/p part of mPlusN[]*/  int j = 0; /* Current index of N[]*/  int k = 0; /* Current index of output mPlusN[]*/  while (k < (m + n))  {  /* Take an element from mPlusN[] if  a) value of the picked element is smaller   and we have not reached end of it  b) We have reached end of N[] */  if ((j == n)||(i < (m + n) && mPlusN[i] <= N[j]))  {  mPlusN[k] = mPlusN[i];  k++;  i++;  }  else // Otherwise take element from N[]  {  mPlusN[k] = N[j];  k++;  j++;  }  } } /* Utility that prints out an array on a line */ void printArray(int arr[], int size) {  for (int i = 0; i < size; i++)  cout << arr[i] << " ";  cout << endl; } /* Driver code */ int main() {  /* Initialize arrays */  int mPlusN[] = {2, 8, NA, NA, NA, 13, NA, 15, 20};  int N[] = {5, 7, 9, 25};    int n = sizeof(N) / sizeof(N[0]);  int m = sizeof(mPlusN) / sizeof(mPlusN[0]) - n;  /*Move the m elements at the end of mPlusN*/  moveToEnd(mPlusN, m + n);  /*Merge N[] into mPlusN[] */  merge(mPlusN, N, m, n);  /* Print the resultant mPlusN */  printArray(mPlusN, m+n);  return 0; }

// C program to Merge an array of  // size n into another array of size m + n #include <stdio.h> /* Assuming -1 is filled for   the places where element  is not available */ #define NA -1 /* Function to move m elements   at the end of array mPlusN[]  */ void moveToEnd(int mPlusN[], int size) {  int i = 0, j = size - 1;  for (i = size - 1; i >= 0; i--)  if (mPlusN[i] != NA) {  mPlusN[j] = mPlusN[i];  j--;  } } /* Merges array N[] of size n into array mPlusN[]  of size m+n*/ void merge(int mPlusN[], int N[], int m, int n) {  int i = n; /* Current index of i/p part of mPlusN[]*/  int j = 0; /* Current index of N[]*/  int k = 0; /* Current index of output mPlusN[]*/  while (k < (m + n))   {  /* Take an element from mPlusN[] if  a) value of the picked element is smaller and we  have not reached end of it  b) We have reached end of N[] */  if ((j == n)|| (i < (m + n)  && mPlusN[i] <= N[j]))   {  mPlusN[k] = mPlusN[i];  k++;  i++;  }  else // Otherwise take element from N[]  {  mPlusN[k] = N[j];  k++;  j++;  }  } } /* Utility that prints out an array on a line */ void printArray(int arr[], int size) {  int i;  for (i = 0; i < size; i++)  printf("%d ", arr[i]);  printf("\n"); } /* Driver code */ int main() {  /* Initialize arrays */  int mPlusN[] = { 2, 8, NA, NA, NA, 13, NA, 15, 20 };  int N[] = { 5, 7, 9, 25 };  int n = sizeof(N) / sizeof(N[0]);  int m = sizeof(mPlusN) / sizeof(mPlusN[0]) - n;  /*Move the m elements at the end of mPlusN*/  moveToEnd(mPlusN, m + n);  /*Merge N[] into mPlusN[] */  merge(mPlusN, N, m, n);  /* Print the resultant mPlusN */  printArray(mPlusN, m + n);  return 0; }

Java

// Java program to Merge an array of  // size n into another array of size m + n class MergeArrays {  /* Function to move m   elements at the end of array  * mPlusN[] */  void moveToEnd(int mPlusN[], int size)  {  int i, j = size - 1;  for (i = size - 1; i >= 0; i--) {  if (mPlusN[i] != -1) {  mPlusN[j] = mPlusN[i];  j--;  }  }  }  /* Merges array N[] of   size n into array mPlusN[]  of size m+n*/  void merge(int mPlusN[], int N[], int m, int n)  {  int i = n;  /* Current index of i/p part of mPlusN[]*/  int j = 0;  /* Current index of N[]*/  int k = 0;  /* Current index of output mPlusN[]*/  while (k < (m + n))  {  /* Take an element from mPlusN[] if  a) value of the picked element is smaller and we  have not reached end of it b) We have reached  end of N[] */  if ((i < (m + n) && mPlusN[i] <= N[j])  || (j == n)) {  mPlusN[k] = mPlusN[i];  k++;  i++;  }  else // Otherwise take element from N[]  {  mPlusN[k] = N[j];  k++;  j++;  }  }  }  /* Utility that prints out an array on a line */  void printArray(int arr[], int size)  {  int i;  for (i = 0; i < size; i++)  System.out.print(arr[i] + " ");  System.out.println("");  }  // Driver Code  public static void main(String[] args)  {  MergeArrays mergearray = new MergeArrays();  /* Initialize arrays */  int mPlusN[] = { 2, 8, -1, -1, -1, 13, -1, 15, 20 };  int N[] = { 5, 7, 9, 25 };  int n = N.length;  int m = mPlusN.length - n;  /*Move the m elements at the end of mPlusN*/  mergearray.moveToEnd(mPlusN, m + n);  /*Merge N[] into mPlusN[] */  mergearray.merge(mPlusN, N, m, n);  /* Print the resultant mPlusN */  mergearray.printArray(mPlusN, m + n);  } } // This code has been contributed by Mayank Jaiswal

Python3

# Python program to Merge an array of  # size n into another array of size m + n NA = -1 # Function to move m elements # at the end of array mPlusN[] def moveToEnd(mPlusN, size): i = 0 j = size - 1 for i in range(size-1, -1, -1): if (mPlusN[i] != NA): mPlusN[j] = mPlusN[i] j -= 1 # Merges array N[] # of size n into array mPlusN[] # of size m+n def merge(mPlusN, N, m, n): i = n # Current index of i/p part of mPlusN[] j = 0 # Current index of N[] k = 0 # Current index of output mPlusN[] while (k < (m+n)): # Take an element from mPlusN[] if # a) value of the picked # element is smaller and we have # not reached end of it # b) We have reached end of N[] */ if ((j == n) or (i < (m+n) and mPlusN[i] <= N[j])): mPlusN[k] = mPlusN[i] k += 1 i += 1 else: # Otherwise take element from N[] mPlusN[k] = N[j] k += 1 j += 1 # Utility that prints # out an array on a line def printArray(arr, size): for i in range(size): print(arr[i], " ", end="") print() # Driver function to # test above functions # Initialize arrays mPlusN = [2, 8, NA, NA, NA, 13, NA, 15, 20] N = [5, 7, 9, 25] n = len(N) m = len(mPlusN) - n # Move the m elements # at the end of mPlusN moveToEnd(mPlusN, m+n) # Merge N[] into mPlusN[] merge(mPlusN, N, m, n) # Print the resultant mPlusN printArray(mPlusN, m+n) # This code is contributed # by Anant Agarwal.

// C# program to Merge an array of // size n into another array of size m + n using System; class GFG {  /* Function to move m elements at  the end of array mPlusN[] */  public virtual void moveToEnd(int[] mPlusN, int size)  {  int i, j = size - 1;  for (i = size - 1; i >= 0; i--)   {  if (mPlusN[i] != -1) {  mPlusN[j] = mPlusN[i];  j--;  }  }  }  /* Merges array N[] of size n  into array mPlusN[] of size m+n*/  public virtual void merge(int[] mPlusN,  int[] N, int m,  int n)  {  int i = n;  /* Current index of i/p  part of mPlusN[]*/  int j = 0;  /* Current index of N[]*/  int k = 0;  /* Current index of output mPlusN[]*/  while (k < (m + n))  {  /* Take an element from mPlusN[] if  a) value of the picked element is smaller  and we have not reached end of it  b) We have reached end of N[] */  if ((j == n)(i < (m + n)   && mPlusN[i] <= N[j]))  {  mPlusN[k] = mPlusN[i];  k++;  i++;  }  else // Otherwise take element from N[]  {  mPlusN[k] = N[j];  k++;  j++;  }  }  }  /* Utility that prints out  an array on a line */  public virtual void printArray(int[] arr, int size)  {  int i;  for (i = 0; i < size; i++) {  Console.Write(arr[i] + " ");  }  Console.WriteLine("");  }  // Driver Code  public static void Main(string[] args)  {  GFG mergearray = new GFG();  /* Initialize arrays */  int[] mPlusN = new int[] { 2, 8, -1, -1, -1,  13, -1, 15, 20 };  int[] N = new int[] { 5, 7, 9, 25 };  int n = N.Length;  int m = mPlusN.Length - n;  /*Move the m elements at the  end of mPlusN*/  mergearray.moveToEnd(mPlusN, m + n);  /*Merge N[] into mPlusN[] */  mergearray.merge(mPlusN, N, m, n);  /* Print the resultant mPlusN */  mergearray.printArray(mPlusN, m + n);  } } // This code is contributed by Shrikant13

PHP

<?php // PHP program to Merge an array  // of size n into another array  // of size m + n /* Assuming -1 is filled for  the places where element is  not available */ $NA = -1; /* Function to move m elements  at the end of array mPlusN[] */ function moveToEnd(&$mPlusN, $size) { global $NA; $j = $size - 1; for ($i = $size - 1; $i >= 0; $i--) if ($mPlusN[$i] != $NA) { $mPlusN[$j] = $mPlusN[$i]; $j--; } } /* Merges array N[] of size n  into array mPlusN[] of size m+n*/ function merge(&$mPlusN, &$N, $m, $n) { $i = $n; /* Current index of i/p   part of mPlusN[]*/ $j = 0; /* Current index of N[]*/ $k = 0; /* Current index of  output mPlusN[]*/ while ($k < ($m + $n)) { /* Take an element from mPlusN[] if  a) value of the picked element   is smaller and we have not  reached end of it  b) We have reached end of N[] */ if (($j == $n) || ($i < ($m + $n) && $mPlusN[$i] <= $N[$j])) { $mPlusN[$k] = $mPlusN[$i]; $k++; $i++; } else // Otherwise take element from N[] { $mPlusN[$k] = $N[$j]; $k++; $j++; } } } /* Utility that prints out  an array on a line */ function printArray(&$arr, $size) { for ($i = 0; $i < $size; $i++) echo $arr[$i] . " "; echo "\n"; } // Driver Code /* Initialize arrays */ $mPlusN = array(2, 8, $NA, $NA, $NA, 13, $NA, 15, 20); $N = array(5, 7, 9, 25); $n = sizeof($N); $m = sizeof($mPlusN) - $n; /* Move the m elements   at the end of mPlusN*/ moveToEnd($mPlusN, $m + $n); /* Merge N[] into mPlusN[] */ merge($mPlusN, $N, $m, $n); /* Print the resultant mPlusN */ printArray($mPlusN, $m+$n); // This code is contributed // by ChitraNayal ?>

JavaScript

<script> // Javascript program to Merge an array of  // size n into another array of size m + n  /* Function to move m   elements at the end of array  * mPlusN[] */  function moveToEnd(mPlusN,size)  {  let i = 0;  let j = size - 1;  for (i = size - 1; i >= 0; i--)  {  if (mPlusN[i] != -1)  {  mPlusN[j] = mPlusN[i];  j--;  }  }  }    /* Merges array N[] of   size n into array mPlusN[]  of size m+n*/  function merge(mPlusN, N, m, n)  {  let i = n;    /* Current index of i/p part of mPlusN[]*/  let j = 0;    /* Current index of N[]*/  let k = 0;    /* Current index of output mPlusN[]*/  while (k < (m + n))  {    /* Take an element from mPlusN[] if  a) value of the picked element is smaller and we  have not reached end of it b) We have reached  end of N[] */  if ((i < (m + n) && mPlusN[i] <= N[j]) || (j == n))  {  mPlusN[k] = mPlusN[i];  k++;  i++;  }  else // Otherwise take element from N[]  {  mPlusN[k] = N[j];  k++;  j++;  }  }  }    /* Utility that prints out an array on a line */  function printArray(arr,size)  {  let i = 0;  for (i = 0; i < size; i++)  {  document.write(arr[i] + " ");  }  document.write("\n");  }    // Driver Code   /* Initialize arrays */  let mPlusN = [2, 8, -1, -1, -1, 13, -1, 15, 20];  let N = [ 5, 7, 9, 25]  let n = N.length;  let m = mPlusN.length - n;    /*Move the m elements at the end of mPlusN*/  moveToEnd(mPlusN, m + n);    /*Merge N[] into mPlusN[] */  merge(mPlusN, N, m, n);    /* Print the resultant mPlusN */  printArray(mPlusN, m + n);    // This code is contributed by avanitrachhadiya2155 </script>