# 10.1. Sorted merge

> You have 2 sorted arrays A and B, and A has a large enough buffer at the end to hold B. Merge B into A in a sorted order

```python
def merge_arrays(a: list, b: list):
	'''
	a = [1, 3, 4, 6]
	b = [2, 5]
	'''
	idx = 0
	b_pos = 0
	while b_pos < len(b):
		while a[idx] < b[b_pos]:
			idx += 1
		a.insert(b[b_pos], idx)
		b_pos += 1
```

This would take O(n) for worst case scenario, where n=len(A), O(m) in best case scenario for m=len(B). Space complexity O(1) because we can store this info in A directly.

## Solution

Simply compare elements of A and B and insert them in order. The only problem is that if we insert an element in the front of A, then we have to shift the existing elements to the back. It's better to insert elements into the back of the array, where there is empty space.

```python
def merge(a, b, lastA, lastB):
	indexA = lastA - 1
	indexB = lastB - 1
	indexMerged = lastA + lastB - 1

	while indexB >= 0:
		# end of A is > than end of B
		if indexA >= 0 and a[indexA] > b[indexB]:
			a[indexMerged] = a[indexA]
			indexA -= 1
		else:
			a[indexMerged] = b[indexB]
			indexB -= 1
		indexMerged -= 1
	return
```
