Given two sorted arrays of length n1 and n2 in ascending order, a1 [] and a2 [].
Merge them in sorted order so that a1[] contains the first n1 elements and a2[] contains the last n2 elements.
Input: a1[] = {1, 3, 5, 7}, a2[] = {0, 2, 6, 8, 9}
Output: a1[] = {1,3,5,7} a2[] = {0,2,6,8,9}
Input: a1[] = {10, 12}, a2[] = {5, 18, 20}
Output: a1[] = {5,10} a2[] = {12,18,20}
Solutions
Method 1: In O(n1*n2) time and O(1) space
In this approach, we iterate the first array a1[] from left to right and whenever we encounter an element that is greater than the first element of a2, i.e, a1[i] > a2 [0], we just swap it and rearrange a2[] in a sorted manner.
Complexity
The time complexity of this solution is O(n1*n2) and space complexity is O(1).