def mergeSort(arr):
    if len(arr) <= 1:
        return arr
    return merge(mergeSort(left(arr)), mergeSort(right(arr)))

def left(arr):
    return arr[0:mid(arr)]

def right(arr):
    return arr[mid(arr):]

def mid(arr):
    return (0 + len(arr)) / 2

def merge(L1, L2): # Basically two-ptr sorted array problem
    i, j = 0, 0
    res = []

    while i < len(L1) and j < len(L2):
        if L1[i] < L2[j]:
            res.append(L1[i])
            i += 1
        else:
            res.append(L2[j])
            j += 1

    res = appendIfRemaining(res, L1, i)
    res = appendIfRemaining(res, L2, j)

    return res

def appendIfRemaining(res, arr, index):
    while index < len(arr):
        res.append(arr[index])
        index += 1
    return res

print(merge([1], [2]))
print(merge([6], [3]))
print(merge([1, 2], [3, 6]))
print(mergeSort([1, 2, 6, 3]))
print(mergeSort([1]))
print(mergeSort([]))
print(mergeSort([-1, -1, 5, 5, 2, 3, 1000]))