DEV Community

Cover image for How to Merge Two Sorted Arrays
Ateev Duggal
Ateev Duggal

Posted on • Originally published at tekolio.com

How to Merge Two Sorted Arrays

Problem

You are given two sorted arrays A and B of lengths m and n, the task is to merge the two sorted arrays in such a way that the merged array is also sorted.

Example

Input
A[] = {3, 9, 10, 18, 23}
B[] = {5, 12, 15, 20, 21, 25}

Output
Merged[] = {3, 5, 9, 10, 12, 15, 18, 20, 21, 23, 25}

Explanation
The merged array is of the size of n + m and contains both the elements of array A and array B in sorted order

Input:
A[] = { 5, 8, 9}
B[] = {4, 7, 8}

Output:
Merged[] = {4, 5, 7, 8, 8, 9}

Explanation
The merged array is of the size of n + m and contains both the elements of array A and array B in sorted order

Index

  1. Brute Force Approach
  2. Insertion Sort Approach
  3. Efficient Approach — Using Merge Sort

Brute Force Approach

The idea is to create a new array C[] of length m+n and put all the elements from A[] and B[] in it and then sort them using Arrays.sort().

Merged Array

Algorithm

  1. Create an array C of n+m size to store the merged array
  2. Put the values of both A and B arrays using a for loop
  3. Sort the C array using Array..sort().

Simple merging of two sorted arrays

Pseudo Code

Int[] solve(int[] A, int[] B, int n, int m) {
Create a new array C of n+m size
while(i<n) {
C[k++] = A[i++];
}
while(j<m) {
C[k++] = B[j++];
}
Sort C;
return C
}
Enter fullscreen mode Exit fullscreen mode

Output

Array after merging - 1 2 3 4 5 6 7 8

Time Complexity — O((m+n) log(m+n))
We have sorted an array of size m+n using Arrays.sort(), and the time complexity of this operation is O(n log n) which in this case becomes O((m+n )log(m+n))

Space Complexity — O(m+n)
We have created a new array C of size n+m which will store the merged sorted array.

Continue Reading…

Top comments (1)

Collapse
 
stevietillis profile image
StevieTillis

Merge sort is one of the most efficient sorting algorithms. get out of jail spell