How to Merge Two Sorted Arrays

Merge Two Sorted Arrays

Problem

Example

InputA[] = {3, 9, 10, 18, 23}B[] = {5, 12, 15, 20, 21, 25}OutputMerged[] = {3, 5, 9, 10, 12, 15, 18, 20, 21, 23, 25}ExplanationThe merged array is of the size of n + m and contains both the elements of array A and array B in sorted orderInput:A[] = { 5, 8, 9}B[] = {4, 7, 8}Output:Merged[] = {4, 5, 7, 8, 8, 9}ExplanationThe 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

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 sizewhile(i<n) {C[k++] = A[i++];}while(j<m) {C[k++] = B[j++];}Sort C;return C}

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…

--

--

Get the Medium app

A button that says 'Download on the App Store', and if clicked it will lead you to the iOS App store
A button that says 'Get it on, Google Play', and if clicked it will lead you to the Google Play store
Ateev Duggal

I am a front-end developer from India with over one year of experience in freelancing with skills like Git, HTML5, CSS3, Bootstrap 4&5, and React.