병합정렬

우선적으로 분할하는 방법
lst의 길이가 1이면 리턴을 걸어준다.
우선적으로 길이를 중앙을 기준으로 왼쪽부터 쭈루룩 나눔
반대로 오른쪽도 쭈루룩 나눔

def merge_sort(lst):
    print(lst)
    if len(lst)==1:
        return lst
    #일단 이분할
    mid = len(lst)//2
    #mid를 인덱스 로
    left =merge_sort(lst[:mid])
    right = merge_sort(lst[mid:])
    return left + right
    # ret = []
    # return ret


arr = [69,30,10,2,16,8,32,21]
merge_sort(arr)

#  결과

[69, 30, 10, 2, 16, 8, 32, 21]
[69, 30, 10, 2]
[69, 30]
[69]
[30]
[10, 2]
[10]
[2]
[16, 8, 32, 21]
[16, 8]
[16]
[8]
[32, 21]
[32]
[21]

def merge_sort(lst):
    # print(lst)
    if len(lst)==1:
        return lst
    #일단 이분할
    mid = len(lst)//2
    #mid를 인덱스 로
    left =merge_sort(lst[:mid])
    right = merge_sort(lst[mid:])


    # 이미 절렬된 상태 합치기위해
    ret = []
    #왼쪽것이 짝으면 왼쪽거 넣고 반대면 오른쪽 빼서넣음
    # 그러면 둘중에 한개는 빈다. 그떄까지한다.
    while left and right: #left riht 둘다 있을떄 까지 돈다.
        if left[0] <right[0]:
            ret.append(left.pop(0))
        else:
            ret.append(right.pop(0))
    #남아있는거 이미정렬된 ret에 넣는다
    ret.extend(left)
    ret.extend(right)
    #원래는 비교 근데 어짜피 빈리스트라 상관ㄴㄴ


    return ret


arr = [69,30,10,2,16,8,32,21]
sorted_lst = merge_sort(arr)
print(sorted_lst)
# 처음에 다부름 절반나눠서
# 왼쪽먼저간다 그래서 또나누기