병합정렬 파이썬(Python)

안녕하세요, 츄르 사려고 코딩하는 집사! 코집사입니다.

 

NUM = int(input())
A = list(map(int, input().split()))

def MergeSort(A): #1
    if len(A) < 2 :
        return A
    
    else :
        mid = len(A)//2
        left = A[:mid]
        right = A[mid:]
    
        l = MergeSort(left)
        r = MergeSort(right)
        return Merge(l, r)

def Merge(left, right) : #2
    i = 0
    j = 0
    B = []
    
    while (i<len(left)) & (j<len(right)) :
        if left[i] < right[j] :
            B.append(left[i])
            i += 1
            
        else :
            B.append(right[j])
            j += 1
            
    while (i<len(left)) :
        B.append(left[i])
        i += 1
    
    while (j<len(right)) :
        B.append(right[j])
        j += 1
    
    return B

print(MergeSort(A))

 

#1 : MergeSort를 재귀하여 1개의 데이터가 있을 때까지 분리

#2 : 1개씩 분리한 데이터들을 비교하여 B라는 리스트에 새로 넣어 정렬