Merge two sorted arrays with O(1) extra space - GeeksforGeeks
We are given two sorted array. We need to merge these two arrays such that the initial numbers (after complete sorting) are in the first array and the remaining numbers are in the second array. Extra space allowed in O(1).
https://www.geeksforgeeks.org/efficiently-merging-two-sorted-arrays-with-o1-extra-space/
Efficiently merging two sorted arrays with O(1) extra space
We are given two sorted array. We need to merge these two arrays such that the initial numbers (after complete sorting) are in the first array and the remaining numbers are in the second array. Extra space allowed in O(1).
This task is simple and O(m+n) if we are allowed to use extra space. But it becomes really complicated when extra space is not allowed and doesn’t look possible in less than O(m*n) worst case time.
The idea is to begin from last element of ar2[] and search it in ar1[]. If there is a greater element in ar1[], then we move last element of ar1[] to ar2[]. To keep ar1[] and ar2[] sorted, we need to place last element of ar2[] at correct place in ar1[]. We can use Insertion Sort type of insertion for this. Below is algorithm:
1) Iterate through every element of ar2[] starting from last
element. Do following for every element ar2[i]
a) Store last element of ar1[i]: last = ar1[i]
b) Loop from last element of ar1[] while element ar1[j] is
smaller than ar2[i].
ar1[j+1] = ar1[j] // Move element one position ahead
j--
c) If any element of ar1[] was moved or (j != m-1)
ar1[j+1] = ar2[i]
ar2[i] = last
The worst case time complexity of code/algorithm is O(m*n). The worst case occurs when all elements of ar1[] are greater than all elements of ar2[].
Efficiently merging two sorted arrays with O(1) extra space
Given two sorted arrays, we need to merge them in O((n+m)*log(n+m)) time with O(1) extra space into a sorted array, when n is the size of the first array, and m is the size of the second array.
Example:
Input: ar1[] = {10};
ar2[] = {2, 3};
Output: ar1[] = {2}
ar2[] = {3, 10}
