[알고리즘/Algorithm] 파이썬으로 병합/합병 정렬(Merge Sort) 알아보기

Merge Sort (병합 정렬)

• 리스트를 절반으로 잘라 비슷한 크기의 리스트 2개로 나눈다.
• 각 부분 리스트를 재귀적으로 병합 정렬을 이용해 정렬한다.
• 두 부분 리스트를 다시 하나의 정렬되 리스트로 병합한다.

 

병합 정렬 흐름 그림

병합 정렬은 그림과 같이 리스트를 분할(split)한 후에 병합(merge)를 반복하며 정렬한다.

 

 

파이썬으로 구현한 병합 정렬

def merge_sort(data):
    return split(data)


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


def merge(left, right):
    merged = list()
    left_point, right_point = 0, 0

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

    # case 2: left만 남아있을 때
    while len(left) > left_point:
        merged.append(left[left_point])
        left_point += 1

    # case 3: right만 남아있을 때
    while len(right) > right_point:
        merged.append(right[right_point])
        right_point += 1

    return merged

위 코드를 보면 함수가 3개 정의되어 있다. 

merge_sort(data) 함수는 단순히 이름을 맞추기 위해 사용된 함수고,

split(data) 함수와 같은 역할이다. 

 

따라서 살펴볼 함수는 2개(split(), merge())이다.

 

1. split(data)

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

split 함수는 이름 그대로 리스트를 나누는 역할을 한다.

리스트의 개수가 1과 같거나 1보다 작으면 재귀적으로 계속해서 mid를 기준으로 left와 right로 나눠지게 되고,

최대로 나눠진 이후에 재귀를 탈출하여 merge 함수를 만나 left와 right가 합쳐지게 된다.

 

2. merge(left, right)

def merge(left, right):
    merged = list()
    left_point, right_point = 0, 0

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

    # case 2: left만 남아있을 때
    while len(left) > left_point:
        merged.append(left[left_point])
        left_point += 1

    # case 3: right만 남아있을 때
    while len(right) > right_point:
        merged.append(right[right_point])
        right_point += 1

    return merged

merge 함수는 기본적으로 left와 right를 받아 정렬된 리스트인 merged를 리턴하는 함수로 심플한 기능을 하는 함수다.

 

left_point와 right_point를 일종의 포인터로 활용하여 left와 right를 순회하며 merged에 요소를 차곡 차곡 추가해주는 역할을 한다.

 

코드가 살짝 긴 이유는 단지 케이스가 3개로 나뉘기 때문인데.. 위 코드의 주석과 같이 

1. left/right가 요소가 남아있을 때
2. left만 남아있을 때
3. right만 남아있을 때

3가지 경우로 나뉜다.

 

1번 케이스에 코드를 살펴보면 while 루프에서 left와 right의 값을 비교하며 작은 것부터 차례대로 

merged에 append해주어 정렬된 리스트를 만든다.

 

그후 1번 케이스를 통과하면 케이스가 위에서 살펴본 케이스 중 2, 3번인 두 개의 경우만 남을 것이다.

 

2번 while 문을 진입한다는 뜻은 left에 요소가 남았다는 뜻이므로 해당 요소를 바로 merged에 append 해주고,

3번 while 문을 진입한다는 뜻은 right에 요소가 남았다는 뜻이므로 해당 요소를 바로 merged에 append 해준다.

 

이렇게 merge 함수를 작성할 수 있다.

 

 

함수 실행 결과

target = [10,7,1,5,6,8,1,2,3]
print(split(target))
# [1, 1, 2, 3, 5, 6, 7, 8, 10]

보다시피 이쁘게 정렬된 리스트를 받을 수 있다.^_^

 

 

시간 복잡도

• 기본적으로는 O(n log n) 이다.