Methods for Merging Two Sorted Arrays

Explore Various Approaches

Given two sorted arrays A[] and B[] of size N & M. The task is to merge both the arrays into a new single array in non-decreasing order.

Get started now

Problem Statement

Example- Input: A[] =[3, 9, 10, 18, 23], B[] = [5, 12, 15, 20, 21, 25]  Output: [3, 5, 9, 10, 12, 15, 18, 20, 21, 23, 25]

Explore more examples

A straightforward method is to merge the elements of one array with the other array and then sort the resulting array.

Want to see code implementation?

Approach 1: Insert and Sort Approach

Time Complexity: O((N + M)log(N+M)), where N and M are sizes of array A[] & B[]  Space Complexity: O(N), built-in sort takes space

Want to explore other approach?

Using the Merge Sort technique is an effective method because both arrays are already sorted. By using this method, we can apply a similar method to merge sort.

Wanna check out algorithm?

Approach 2: Merge Sort Method

Algorithm 1. Create an auxiliary array of size N + M.  2. Initialize two pointers i & j to 0. 3. Pointer i points to 1st array, whereas pointer j points to 2nd array.

Check further steps

Time Complexity: O(N + M), where N and M is the size of array A[] & B[]  Space Complexity: O(N + M), as the auxiliary array is used.

Want to see code implementation?

Start your journey now and learn how to merge two sorted arrays with code implementation.

Ready to level up your coding skills?

Step Up Your Game with InterviewBit Web Stories

Don't miss out on the chance to upskill yourself with IntervewBit's engaging web stories. 

“