43 lines
1.1 KiB
Markdown
43 lines
1.1 KiB
Markdown
# 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
|
|
```
|