def merge_sort(arr):
    # 병합하기 위한 함수로 입력된 배열은 오름차순으로 정렬된다.
    
    # 병합의 최소 조건은 배열의 크기가 2 이상
    if len(arr) <= 1:
        return arr
    
    # 분할 지점 설정 
    mid = len(arr) // 2
    left = arr[:mid]
    right = arr[mid:]
    
    # 재귀적으로 분할된 구역을 나눈다.
    left = merge_sort(left)
    right = merge_sort(right)
    
    return merge( left, right )

def merge(left, right):
    # 정렬하기 위한 함수로 입련된 두 개의 배열을 순차적으로 비교해가면 하나의 새로운 오름차순으로 정렬된 배열을 만든다.
    
    result = [] # 정렬된 숫자
    i = 0 # left index
    j = 0 # right index
    
    # 한쪽씩 비교하면서 작은 수를 result에 집어 넣는다.
    while i < len(left) and j < len(right) :
        if left[i] <= right[j] :
            result.append(left[i])
            i += 1
        else:
            result.append(right[j])
            j+=1
    
    # 남은 것이 있으면 result에 추가 정리
    result += left[i:]
    result += right[j:]
    
    return result