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

Out[2]:

([2, 7, 10], [5, 8, 12, 14, 22, 33])

In [3]:

mergeSortedArrays(arrB, arrA)

Out[3]:

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

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

Out[4]:

(['NA', 'NA', 'NA', 'NA', 'NA', 'NA', 2, 7, 10], [5, 8, 12, 14, 22, 33])

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)

Out[6]:

([2, 5, 7, 8, 10, 12, 14, 22, 33], [5, 8, 12, 14, 22, 33])