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
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
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
- 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
- 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
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
- 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