Given two sorted arrays arr1 and arr2 of sizes N and M in non-decreasing order. Merge them in sorted order without using any extra space. Modify arr1 so that it contains the first N elements and modify arr2 so that it contains the last M elements.
N = 4, arr1 = [1 3 5 7]
M = 5, arr2 = [0 2 6 8 9]
arr1 = [0 1 2 3]
arr2 = [5 6 7 8 9]
Explanation: After merging the two
non-decreasing arrays, we get,
0 1 2 3 5 6 7 8 9.
N = 2, arr1 = [10, 12]
M = 3, arr2 = [5 18 20]
arr1 = [5 10]
arr2 = [12 18 20]
Explanation: After merging two sorted arrays
we get 5 10 12 18 20.
You don't need to read input or print anything. You only need to complete the function merge() that takes arr1, arr2, N and M as input parameters and modifies them in-place so that they look like the sorted merged array when concatenated.
Expected Time Complexity: O((n+m) log(n+m))
Expected Auxilliary Space: O(1)
1 <= X, Y <= 5*104
0 <= arr1i, arr2i <= 109
There are 3 approach to solve this question.
1st the brute force approach in this case you will use one extra array of size(m+n ) and insert which element is smaller.
you will iterate over array 1 and every time you will compare ith element with array2 element and if arr1[i] > arr2 you will swap them and apply insertion sort in
This is most efficient method
The idea: We start comparing elements that are far from each other rather than adjacent.
For every pass, we calculate the gap and compare the elements towards the right of the gap. Every pass, the gap reduces to the ceiling value of dividing by 2
credit - gfg