Given two sorted arrays, arr[], brr[] of size N, and M, the task is to merge the two given arrays such that they form a sorted sequence of integers combining elements of both the arrays.
Examples:
Input: arr[] = {10}, brr[] = {2, 3}
Output: 2 3 10
Explanation: The merged sorted array obtained by taking all the elements from the both the arrays is {2, 3, 10}.
Therefore, the required output is 2 3 10.Input: arr[] = {1, 5, 9, 10, 15, 20}, brr[] = {2, 3, 8, 13}
Output: 1 2 3 5 8 9 10 13 15 20
Naive Approach: Refer to Merge two sorted arrays for the simplest approach to merge the two given arrays.
Time Complexity: O(N * M)
Auxiliary Space: O(1)
Space Optimized Approach: Refer to Merge two sorted arrays with O(1) extra space to merge the two given arrays without using any extra memory.
Time Complexity: O(N * M)
Auxiliary Space: O(1)
Efficient Space Optimized Approach: Refer to Efficiently merging two sorted arrays with O(1) extra space to merge the two given array without using any extra memory.
Time Complexity: O((N + M) * log(N + M))
Auxiliary Space: O(1)
Heap – based Approach: The problem can be solved using Heap. The idea is to traverse arr[] array and compare the value of arr[i] with brr[0] and check if arr[i] is greater than brr[0] or not. If found to be true then swap(arr[i], brr[0) and perform the heapify operation on brr[]. Follow the steps below to solve the problem:
- Traverse the array arr[] and compare the value of arr[i] with brr[0] and check if arr[i] is greater than brr[0] or not. If found to be true then swap(arr[i], brr[0) and perform the heapify operation on brr[].
- Finally, sort the array brr[] and print both arrays.
Below is the implementation of the above approach:
C++
// C++ program to implement// the above approach#include <bits/stdc++.h>using namespace std;// Function to perform min heapify// on array brr[]void minHeapify(int brr[], int i, int M){ // Stores index of left child // of i. int left = 2 * i + 1; // Stores index of right child // of i. int right = 2 * i + 2; // Stores index of the smallest element // in (arr[i], arr[left], arr[right]) int smallest = i; // Check if arr[left] less than // arr[smallest] if (left < M && brr[left] < brr[smallest]) { // Update smallest smallest = left; } // Check if arr[right] less than // arr[smallest] if (right < M && brr[right] < brr[smallest]) { // Update smallest smallest = right; } // if i is not the index // of smallest element if (smallest != i) { // Swap arr[i] and arr[smallest] swap(brr[i], brr[smallest]); // Perform heapify on smallest minHeapify(brr, smallest, M); }}// Function to merge two sorted arraysvoid merge(int arr[], int brr[], int N, int M){ // Traverse the array arr[] for (int i = 0; i < N; ++i) { // Check if current element // is less than brr[0] if (arr[i] > brr[0]) { // Swap arr[i] and brr[0] swap(arr[i], brr[0]); // Perform heapify on brr[] minHeapify(brr, 0, M); } } // Sort array brr[] sort(brr, brr + M);}// Function to print array elementsvoid printArray(int arr[], int N){ // Traverse array arr[] for (int i = 0; i < N; i++) cout << arr[i] << " ";}// Driver Codeint main(){ int arr[] = { 2, 23, 35, 235, 2335 }; int brr[] = { 3, 5 }; int N = sizeof(arr) / sizeof(arr[0]); int M = sizeof(brr) / sizeof(brr[0]); // Function call to merge // two array merge(arr, brr, N, M); // Print first array printArray(arr, N); // Print Second array. printArray(brr, M); return 0;} |
Java
// Java program to implement// the above approachimport java.util.*;class GFG{// Function to perform // min heapify on array // brr[]static void minHeapify(int brr[], int i, int M){ // Stores index of left // child of i. int left = 2 * i + 1; // Stores index of right // child of i. int right = 2 * i + 2; // Stores index of the smallest // element in (arr[i], arr[left], // arr[right]) int smallest = i; // Check if arr[left] less than // arr[smallest] if (left < M && brr[left] < brr[smallest]) { // Update smallest smallest = left; } // Check if arr[right] less // than arr[smallest] if (right < M && brr[right] < brr[smallest]) { // Update smallest smallest = right; } // if i is not the index // of smallest element if (smallest != i) { // Swap arr[i] and // arr[smallest] int temp = brr[i]; brr[i] = brr[smallest]; brr[smallest] = temp; // Perform heapify on smallest minHeapify(brr, smallest, M); }}// Function to merge two // sorted arraysstatic void merge(int arr[], int brr[], int N, int M){ // Traverse the array arr[] for (int i = 0; i < N; ++i) { // Check if current element // is less than brr[0] if (arr[i] > brr[0]) { // Swap arr[i] and brr[0] int temp = arr[i]; arr[i] = brr[0]; brr[0] = temp; // Perform heapify on brr[] minHeapify(brr, 0, M); } } // Sort array brr[] Arrays.sort(brr);}// Function to print array // elementsstatic void printArray(int arr[], int N){ // Traverse array arr[] for (int i = 0; i < N; i++) System.out.print(arr[i] + " ");}// Driver Codepublic static void main(String[] args){ int arr[] = {2, 23, 35, 235, 2335}; int brr[] = {3, 5}; int N = arr.length; int M = brr.length; // Function call to merge // two array merge(arr, brr, N, M); // Print first array printArray(arr, N); // Print Second array. printArray(brr, M);}}// This code is contributed by Rajput-Ji |
Python3
# Python3 program to implement# the above approach# Function to perform min heapify# on array brr[] def minHeapify(brr, i, M): # Stores index of left child # of i. left = 2 * i + 1 # Stores index of right child # of i. right = 2 * i + 2 # Stores index of the smallest element # in (arr[i], arr[left], arr[right]) smallest = i # Check if arr[left] less than # arr[smallest] if (left < M and brr[left] < brr[smallest]): # Update smallest smallest = left # Check if arr[right] less than # arr[smallest] if (right < M and brr[right] < brr[smallest]): # Update smallest smallest = right # If i is not the index # of smallest element if (smallest != i): # Swap arr[i] and arr[smallest] brr[i], brr[smallest] = brr[smallest], brr[i] # Perform heapify on smallest minHeapify(brr, smallest, M)# Function to merge two sorted arraysdef merge(arr, brr, N, M): # Traverse the array arr[] for i in range(N): # Check if current element # is less than brr[0] if (arr[i] > brr[0]): # Swap arr[i] and brr[0] arr[i], brr[0] = brr[0], arr[i] # Perform heapify on brr[] minHeapify(brr, 0, M) # Sort array brr[] brr.sort()# Function to print array elementsdef printArray(arr, N): # Traverse array arr[] for i in range(N): print(arr[i], end = " ")# Driver codeif __name__ == '__main__': arr = [ 2, 23, 35, 235, 2335 ] brr = [3, 5] N = len(arr) M = len(brr) # Function call to merge # two array merge(arr, brr, N, M) # Print first array printArray(arr, N) # Print Second array. printArray(brr, M)# This code is contributed by Shivam Singh |
C#
// C# program to implement// the above approachusing System;class GFG{// Function to perform // min heapify on array // brr[]static void minHeapify(int []brr, int i, int M){ // Stores index of left // child of i. int left = 2 * i + 1; // Stores index of right // child of i. int right = 2 * i + 2; // Stores index of the smallest // element in (arr[i], arr[left], // arr[right]) int smallest = i; // Check if arr[left] less than // arr[smallest] if (left < M && brr[left] < brr[smallest]) { // Update smallest smallest = left; } // Check if arr[right] less // than arr[smallest] if (right < M && brr[right] < brr[smallest]) { // Update smallest smallest = right; } // If i is not the index // of smallest element if (smallest != i) { // Swap arr[i] and // arr[smallest] int temp = brr[i]; brr[i] = brr[smallest]; brr[smallest] = temp; // Perform heapify on smallest minHeapify(brr, smallest, M); }}// Function to merge two // sorted arraysstatic void merge(int []arr, int[]brr, int N, int M){ // Traverse the array []arr for(int i = 0; i < N; ++i) { // Check if current element // is less than brr[0] if (arr[i] > brr[0]) { // Swap arr[i] and brr[0] int temp = arr[i]; arr[i] = brr[0]; brr[0] = temp; // Perform heapify on brr[] minHeapify(brr, 0, M); } } // Sort array brr[] Array.Sort(brr);}// Function to print array // elementsstatic void printArray(int []arr, int N){ // Traverse array []arr for(int i = 0; i < N; i++) Console.Write(arr[i] + " ");}// Driver Codepublic static void Main(String[] args){ int []arr = { 2, 23, 35, 235, 2335 }; int []brr = {3, 5}; int N = arr.Length; int M = brr.Length; // Function call to merge // two array merge(arr, brr, N, M); // Print first array printArray(arr, N); // Print Second array. printArray(brr, M);}}// This code is contributed by Amit Katiyar |
Javascript
<script>// Javascript program to implement// the above approach// Function to perform min heapify// on array brr[]function minHeapify(brr, i, M){ // Stores index of left child // of i. let left = 2 * i + 1; // Stores index of right child // of i. let right = 2 * i + 2; // Stores index of the smallest element // in (arr[i], arr[left], arr[right]) let smallest = i; // Check if arr[left] less than // arr[smallest] if (left < M && brr[left] < brr[smallest]) { // Update smallest smallest = left; } // Check if arr[right] less than // arr[smallest] if (right < M && brr[right] < brr[smallest]) { // Update smallest smallest = right; } // if i is not the index // of smallest element if (smallest != i) { // Swap arr[i] and arr[smallest] let temp = brr[i]; brr[i] = brr[smallest]; brr[smallest] = temp; // Perform heapify on smallest minHeapify(brr, smallest, M); }}// Function to merge two sorted arraysfunction merge(arr, brr, N, M){ // Traverse the array arr[] for (let i = 0; i < N; ++i) { // Check if current element // is less than brr[0] if (arr[i] > brr[0]) { // Swap arr[i] and brr[0] let temp = arr[i]; arr[i] = brr[0]; brr[0] = temp; // Perform heapify on brr[] minHeapify(brr, 0, M); } } // Sort array brr[] brr.sort();}// Function to print array elementsfunction printArray(arr, N){ // Traverse array arr[] for (let i = 0; i < N; i++) document.write(arr[i] + " ");}// Driver Code let arr = [ 2, 23, 35, 235, 2335 ]; let brr = [ 3, 5 ]; let N = arr.length; let M = brr.length; // Function call to merge // two array merge(arr, brr, N, M); // Print first array printArray(arr, N); // Print Second array. printArray(brr, M);//This code is contributed by Mayank Tyagi</script> |
Output:
2 3 5 23 35 235 2335
Time Complexity: O((N + M) * log (M))
Auxiliary Space: O(1)
Efficient Approach: Refer to merge two sorted arrays to efficiently merge the two given arrays.
Time Complexity: O(N + M)
Auxiliary Space: O(N + M)
Feeling lost in the world of random DSA topics, wasting time without progress? It’s time for a change! Join our DSA course, where we’ll guide you on an exciting journey to master DSA efficiently and on schedule.
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
