mergeSortedArrays

# mergeSortedArrays([0,3,4,31], [4,6,30]);
# [0,3,4,4,6,30,31]

# inputs: two arrays
# outputs: one merged array

# option1: append the array, sort the resulting array o(n²)
# option2: optimization

def mergeSortedArrays(Arr, Brr):
    # validate input
    output_array = []
    
    while (len(Arr) or len(Brr)) > 0:
        if len(Arr) == 0:
            output_array.append(Brr[0])
            if len(Brr) != 0:
                Brr.pop(0)
        elif len(Brr) == 0:
            output_array.append(Arr[0])
            if len(Arr) != 0:
                Arr.pop(0);
        elif Arr[0] < Brr[0]:
            output_array.append(Arr[0])
            if len(Arr) != 0:
                Arr.pop(0);
        else:
            output_array.append(Brr[0])
            if len(Brr) != 0:
                Brr.pop(0)
    
    return output_array



print("Hello World!")
sample_arrayA = [0,3,4,31]
sample_arrayB = [4,6,30]

result1 = mergeSortedArrays(sample_arrayA, sample_arrayB)
# print(result1)
assert(result1==[0,3,4,4,6,30,31])

sample_arrayA = [0,3,3,3]
sample_arrayB = [3,3,4,6,30]
result2 = mergeSortedArrays(sample_arrayA, sample_arrayB)
assert(result2 == [0,3,3,3,3,3,4,6,30])


print("Goodbye Cruel World")