병합 정렬 코드 짰는데

왜 자꾸 시간 초과가 뜰까요??


#A = [42,32,24,60,15,5,90,45]

N = int(input())

A = [0]*N

for i in range(N):

    A[i] = int(input())

   

def division(lst):

    

    if len(lst) == 1:

        return lst

  

    mid = len(lst)//2

  

    left = []

    right = []

  

    for i in range(0, mid):

        left.append(lst[i])

    for i in range(mid, len(lst)):

        right.append(lst[i])


    return merge(division(left), division(right))


def merge(left_lst, right_lst):


    result = []

  

    first_index = 0

    second_index = 0


    while first_index < len(left_lst) and second_index < len(right_lst):

        if left_lst[first_index] < right_lst[second_index]:

            result.append(left_lst[first_index])

            first_index += 1

        else:

            result.append(right_lst[second_index])

            second_index += 1


    if first_index < len(left_lst):

        for i in range(first_index, len(left_lst)):

            result.append(left_lst[i])


    if second_index < len(right_lst):

        for i in range(second_index, len(right_lst)):

            result.append(right_lst[i])

    return result


S = division(A)

for i in S:

    print(i)