#!/usr/bin/env python
# coding: utf-8

# # Merge Sorted Arrays

# ## Into Third Array: O(n) - O(m + n)

# In[1]:


def mergeSortedArrays(arrA, arrB):
    resArr = []
    
    l = len(arrA) if len(arrA) <= len(arrB) else len(arrB);
    
    for i in range(l):
        if arrA[i] <= arrB[i]:
            resArr.append(arrA[i])
            resArr.append(arrB[i])
        else:
            resArr.append(arrB[i])
            resArr.append(arrA[i])
            
    if len(arrA) < len(arrB):
        resArr += arrB[len(arrA):]
    elif len(arrB) < len(arrA):
        resArr += arrA[len(arrB):]
    
    return resArr


# In[2]:


arrA = [2, 7, 10]
arrB = [5, 8, 12, 14, 22, 33]

arrA, arrB


# In[3]:


mergeSortedArrays(arrB, arrA)


# ## Into First Array: O(n) - O(m + n)

# In[4]:


arrA = [2, 7, 10]
arrB = [5, 8, 12, 14, 22, 33]

# Make space in first array
arrA = ['NA'] * len(arrB) + arrA

arrA, arrB


# In[5]:


def mergeSortedArraysIntoFirst(arrA, arrB):
    j = len(arrB)
    k = 0
    
    for i in range(len(arrA)):
        if j < len(arrA) and arrA[j] <= arrB[k]:
            arrA[i] = arrA[j]
            j += 1
        else:
            arrA[i] = arrB[k]
            k += 1
    
    return arrA, arrB


# In[6]:


mergeSortedArraysIntoFirst(arrA, arrB)