# Merge two Sorted Arrays Without Extra Space

[Question]: Given two sorted arrays arr1[] and arr2[] ofsizes 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.

Example 1:

```Input:
n = 4, arr1[] = [1 3 5 7]
m = 5, arr2[] = [0 2 6 8 9]
Output:
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.```

Example 2:

```Input:
n = 2, arr1[] = [10 12]
m = 3, arr2[] = [5 18 20]
Output:
arr1[] = [5 10]
arr2[] = [12 18 20]
Explanation:
After merging two sorted arrays
we get 5 10 12 18 20.```
``````/**
Time Complexity: O((n+m)*log(n+m)), where n and m are the sizes of the given arrays.
Reason: The gap is ranging from n+m to 1 and every time the gap gets divided by 2. So, the time complexity of the outer loop will be O(log(n+m)). Now, for each value of the gap, the inner loop can at most run for (n+m) times. So, the time complexity of the inner loop will be O(n+m). So, the overall time complexity will be O((n+m)*log(n+m)).

Space Complexity: O(1) as we are not using any extra space.
*/
func mergeTowSortedArrays(_ arr1: inout [Int], _ arr2: inout [Int], _ n: Int, _ m: Int) {

var len = n + m
var gap = len / 2

while gap > 0 {
var left = 0
var right = left + gap

while right < len {
if left < n && right >= n {
swapIfGreater(&arr1, &arr2, left, right - n)
} else if left >= n {
var newArr2 = arr2
swapIfGreater(&arr2, &newArr2, left - n, right - n)
} else {
var newArr1 = arr1
swapIfGreater(&arr1, &newArr1, left, right)
}
left += 1
right+=1
}

if gap == 1 { break }

gap = (gap / 2) + (gap % 2)

}

func swapIfGreater(_ arr1: inout [Int], _ arr2: inout [Int], _ ind1: Int, _ ind2: Int) {
if arr1[ind1] > arr2[ind2] {
(arr1[ind1], arr2[ind2]) = (arr2[ind2], arr1[ind1])
}
}
}

var arr1 = [1, 4, 8, 10]
var arr2 = [2, 3, 9]
var n = 4, m = 3

mergeTowSortedArrays(&arr1, &arr2, n, m)

print("The merged arrays are:--", arr1, arr2)// [1, 2, 3, 4] [8, 9, 10]``````