- Prepare
- All Platforms
- Programming
- Aptitude
- Syllabus
- Interview Preparation
- Interview Exp.
- Off Campus
- Prime Video
- Prime Mock

- PrepInsta Prime
- OffCampus
- Internship
- Placement Stats
- Prime Video
- Prime Mock

^{0}Notifications Mark All Read

No New notification

- Login
- Get Prime

# Merge Sorted Array

## Understanding Merge Sorted Array

Combining two sorted arrays or Merge Sorted Array is a frequent challenge in Data Structure and Algorithms. This undertaking entails merging two arrays that are already arranged in ascending order into a unified, sorted array. This process proves especially valuable in situations where data from multiple origins must be amalgamated while preserving a sorted sequence.

**Introduction to Merge Sorted Array
**

**Introduction to Merge Sorted Array**

**
Initialization
Begin with two sorted arrays, let's call them Array A and Array B .
Comparison and Merging
Start comparing elements from the end of both arrays. Select the larger of the two elements and place it at the end of the merged array. Move backward through the arrays, comparing and placing elements until the entire merged array is populated.
Completion
Continue this process until all elements from both arrays are merged into the final array, which is often the same array as the one used for merging.
**

Merging Sorted Array is a fundamental algorithmic operation which involves combining two arrays, both of which are already sorted in ascending order, into a single sorted array.

- The goal is to efficiently merge these arrays while maintaining the ascending order of elements.

**This process involves three steps :**

**
****Problem Statement**

**Problem Statement**

Given two sorted arrays, A and B, of sizes m and n respectively, the task is to merge these arrays into a single sorted array. The resulting array should contain all elements from both arrays in sorted order. The final merged array should be placed in the array A, and it should have a total size of m + n.

**Example : **

**Input : **

Array A: [1, 2, 3, 0, 0, 0] m = 3 Array B: [2, 5, 6] n = 3

**Output : **

Array A: [1, 2, 2, 3, 5, 6]

**
****Approach of Merge Sorted Array**

**Approach of Merge Sorted Array**

- One way to solve this problem efficiently is to start from the end of both arrays A and B (since we have extra space at the end of array A) and compare the elements.
- We can then place the larger of the two elements at the end of array A.
- This process continues until we have merged all elements from both arrays into array A in sorted order.

**
****Pseudocode of Merge Sorted Array**

**Pseudocode of Merge Sorted Array**

- Set pointers i, j, and k to the end of arrays A, B, and the merged portion of A respectively.
- While i and j are greater than or equal to 0:

a. If A[i] > B[j], set A[k] = A[i] and decrement i and k.

b. Otherwise, set A[k] = B[j] and decrement j and k. - If there are remaining elements in array B, copy them to the beginning of array A.

**
****Implementation of Merging Two Sorted Array**

**Implementation of Merging Two Sorted Array**

**Input : **

def merge_sorted_array(A, m, B, n): i, j, k = m-1, n-1, m+n-1 while i >= 0 and j >= 0: if A[i] > B[j]: A[k] = A[i] i -= 1 else: A[k] = B[j] j -= 1 k -= 1 while j >= 0: A[k] = B[j] j -= 1 k -= 1 # Example usage A = [1, 2, 3, 0, 0, 0] m = 3 B = [2, 5, 6] n = 3 merge_sorted_array(A, m, B, n) print("Merged Array A:", A)

**Output :**

Merged Array A: [1, 2, 2, 3, 5, 6]

**Explanation : **

- The initial arrays are:

**Array A: [1, 2, 3, 0, 0, 0] with m = 3**

**Array B: [2, 5, 6] with n = 3**

- After the merge_sorted_array function is called, the elements from arrays A and B are merged into A, resulting in the sorted array:
**Merged Array A: [1, 2, 2, 3, 5, 6]**

**
****Complexity Analysis**

**Complexity Analysis**

- The time complexity of this approach is O(m + n), where m and n are the sizes of arrays A and B, respectively.
- This is because we iterate through each element in both arrays once. The space complexity is O(1) since we are modifying array A in-place.

**To wrap it up:**

Merging sorted arrays is a fundamental problem in programming, and understanding the efficient algorithms to solve it is crucial for writing optimized and scalable code. The approach described here ensures that the merged array is created in-place, minimizing the need for additional memory.

Feel free to use the provided pseudocode and implementation as a reference when tackling similar problems or interview questions.

**
**

### Prime Course Trailer

### Related Banners

Get PrepInsta Prime & get Access to all 200+ courses offered by PrepInsta in One Subscription

**Get over 200+ course One Subscription**

Courses like AI/ML, Cloud Computing, Ethical Hacking, C, C++, Java, Python, DSA (All Languages), Competitive Coding (All Languages), TCS, Infosys, Wipro, Amazon, DBMS, SQL and others

Login/Signup to comment