# divide and conquer approach
def mergeSort(array):
    # divides the array into sub-parts
    length = len(array)
    if length == 1 or length == 0:
        # returns leaf node
        return array
    # obtain mid index
    mid = length // 2
    # obtain left array
    leftArray = mergeSort(array[0: mid])
    # obtain right array
    rightArray = mergeSort(array[mid: length])
    # sort left and right array
    return sortedMerge(leftArray, rightArray)

# conquer approach
def sortedMerge(leftArray, rightArray):
    # combines 2 arrays passed
    # initial setup
    leftArrayLength = len(leftArray)
    rightArrayLength = len(rightArray)
    sortedArray = []
    leftIndex = 0
    rightIndex = 0
    
    while leftIndex < leftArrayLength and rightIndex < rightArrayLength:
        # If left array element smaller than right array element
        # add left array element
        if leftArray[leftIndex] < rightArray[rightIndex]:
            sortedArray.append(leftArray[leftIndex])
            # increment leftIndex
            leftIndex += 1
        else:
            # right array element smaller than left array element
            # add right array element
            sortedArray.append(rightArray[rightIndex])
            # increment rightIndex
            rightIndex += 1     

    # append remaining left softed array     
    while leftIndex < leftArrayLength:
        sortedArray.append(leftArray[leftIndex])
        # increment leftIndex
        leftIndex += 1

    # append remaining right softed array
    while rightIndex < rightArrayLength:
        sortedArray.append(rightArray[rightIndex])
        # increment leftIndex
        rightIndex += 1  

    return sortedArray