def mergesort(List):
    """ input : List, an integer list
        output : an sorted integer list
    """
    n = len(List)
    if n == 0 or n==1:
        return List
    first = mergesort(List[:n/2])
    second =  mergesort(List[n/2:])
    i=0
    j=0
    output = []
    while True:
        if first[i]<second[j]:
            output.append(first[i])
            i += 1
        else:
            output.append(second[j])
            j += 1
        if i >= len(first):
            output += second[j:]
                
            break
        if j >= len(second):
            output += first[i:]
                
            break
        
    return output