def mergeSort( aList ):
    """
    Mergesort recursively divide the list into half, sort both halves
    and then merge the two sorted lists into one.
    """
    # If the aList is size 0 or 1, it's already sorted.
    if len( aList ) <= 1:
        return aList

    else:
        mid = len( aList ) // 2

        # Recursively sort the left and right halves
        left = mergeSort( aList[ :mid ] )
        right = mergeSort( aList[mid:] )
        
        # Merge the two (each sorted) parts back together
#        return merge( left, right )
        return mergelist( left, right ) # slightly different version of merge 
                          
def merge( left, right ):
    """
    Merge to sorted list, left and right, into one sorted list.
    """
    aList = []
    lt = 0
    rt = 0

    # Repeatedly move the smallest of left and right to the new list
    while lt < len( left ) and rt < len( right ):
        if left[ lt ] < right[ rt ]:
            aList.append( left[ lt ]  )
            lt += 1
        else:
            aList.append( right[ rt ] )
            rt += 1

    # There will only be elements left in one of the original two lists.

    # Append the remains of left (lt..end) on to the new list.
    while lt < len(left):
        aList.append( left[ lt ] )
        lt += 1
         
    # Append the remains of right (rt..end) on to the new list.
    while rt < len( right ):
        aList.append( right[ rt ] )
        rt += 1

    return aList

def mergelist( left, right ):
    """
    Mergeto sorted list, left and right, into one sorted list.
    """
    aList = [None for x in range(len(left) + len(right))]
    lt = 0
    rt = 0
    i = 0

    # Repeatedly move the smallest of left and right to the new list
    while lt < len( left ) and rt < len( right ):
        if left[ lt ] < right[ rt ]:
            aList[ i ] = left[ lt ]
            lt += 1
        else:
            aList[ i ] = right[ rt ]
            rt += 1
        i += 1

    # There will only be elements left in one of the original two lists.

    # Append the remains of left (lt..end) on to the new list.
    while lt < len(left):
        aList[ i ] = left[ lt ]
        lt += 1
        i += 1
         
    # Append the remains of right (rt..end) on to the new list.
    while rt < len( right ):
        aList[ i ]= right[ rt ]
        rt += 1
        i += 1

    return aList