병합 정렬(Merge Sort)

병합 정렬이란?

• 분할 정복 기법 + 재귀 알고리즘을 이용한 정렬 알고리즘이다. 즉, 주어진 배열을 원소가 하나 밖에 남지 않을 때까지 계속 둘로 쪼갠 후에 다시 크기 순으로 재배열 하면서 원래 크기의 배열로 합칩니다.
• 전반적으로 반복의 수는 점점 절반으로 줄어들기 때문에 O(logN)시간이 필요하며, 각 패스에서 병합할때 모든 값들을 비교해야 하므로 O(N)시간이 소모됩니다. 따라서 총 시간 복잡도는 O(NlogN)입니다.
• 두 개의 배열을 병합할 때 병합 결과를 담아 놓을 배열이 추가로 필요합니다. 따라서 공간 복잡도는 O(N)입니다.

전개

1. 리스트의 길이가 1이하이면 이미 정렬된 것으로 본다. 그렇지 않은 경우에는
2. 분할(divide) : 정렬되지 않은 배열을 재귀적으로 절반으로 잘라 비슷한 크기의 두 부분 배열로 길이가 1이 될 때까지 나눈다.
3. 정복(conquer) : 각 부분 배열을 재귀적으로 병합 정렬을 이용해 정렬한다.
4. 결합(combine) : 두 부분 배열을 다시 하나의 정렬된 배열로 합병한다.

분할 정복(divide and conquer): 큰 문제를 작은 문제로 나누어(분할하여 푸는 (정복하는)방법)

코드

def merge_sort(data):
    return split(data)

def split(data):
    if len(data) <= 1:
        return data
    mid = len(data) // 2
    left = split(data[:mid])
    right = split(data[mid:])
    return merge(left,right)

def merge(left,right):
    temp = []
    l, h = 0,0

    # case 1: left/right가 아직 남아있을 때
    while l < len(left) and h < len(right):
        if left[l] > right[h]:
            temp.append(right[h])
            h+=1
        else:
            temp.append(left[l])
            l+=1

    # case 2: left만 남아있을 때
    while l < len(left):
        temp.append(left[l])
        l+=1

    # case 3: right만 남아있을 때
    while h < len(right):
        temp.append(right[h])
        h+=1
    return temp


if __name__ == '__main__':
    data = [6, 5, 3, 1, 8, 7, 2, 4]
    print(merge_sort(data))

출력

4
2
1
split: [6] [5]
merge: [6] [5]
합병: [5, 6]: 

1
split: [3] [1]
merge: [3] [1]
합병: [1, 3]: 

split: [5, 6] [1, 3]
merge: [5, 6] [1, 3]
합병: [1, 3, 5, 6]: 

2
1
split: [8] [7]
merge: [8] [7]
합병: [7, 8]: 

1
split: [2] [4]
merge: [2] [4]
합병: [2, 4]: 

split: [7, 8] [2, 4]
merge: [7, 8] [2, 4]
합병: [2, 4, 7, 8]: 

split: [1, 3, 5, 6] [2, 4, 7, 8]
merge: [1, 3, 5, 6] [2, 4, 7, 8]
합병: [1, 2, 3, 4, 5, 6, 7, 8]: 

[1, 2, 3, 4, 5, 6, 7, 8]