[Python] 병합 정렬 쉽게 이해하기

정렬의 종류는 다양하다. 그중에 병합 정렬을 쉽게 이해하기 위한 글을 작성해봤다. 

 

 

1. 병합 정렬 

병합 정렬은 Big O 시간 복잡도는 O(n log n) 의 복잡도가 나온다. 

 

아래 사진과 같은 방법으로 소팅한다. 

(사진 출처 : '모두의 알고리즘 with 파이썬' 책)

'모두의 알고리즘 with 파이썬' 책에 그림으로 소팅 과정을 쉽게 설명되어있다. 

1. 리스트를 절반으로 나눕니다. 

2. 1에서 나눈 리스트를 정렬합니다. (이곳에서 재귀함수 사용)

3. 각각의 리스트에서 가장 앞의 인원을 비교해서 작은 인원을 정렬합니다. (계속 반복)

 

 

2. 병합 정렬 소스코드 구현

소스 코드로 구현하면 아래와 같습니다. 

혹시 재귀함수에 대해서 모르시는 분을 위해서 링크를 걸어두겠습니다. ([Python] 재귀함수 간단예제 - 팩토리얼 구현)

소스 코드

# 1. 병합 sort 

def merge_sort(list):

    length = len(list)

 

    # 1) 재귀 함수로 사용하기 위해 종료 조건 만들기

    if length<=1:

        return list

 

    # 2) 리스트 중간을 기준으로 2개로 나누면서, 재귀함수 호출

    mid = length//2

    slist1 = merge_sort(list[:mid])

    slist2 = merge_sort(list[mid:])

 

    # 3) 리스트의 맨 앞자리를 비교하면서 작은것을 result에 추가하기

    result = []

    while slist1 and slist2:

        if slist1[0] < slist2[0]:

            result.append(slist1.pop(0))

        else:

            result.append(slist2.pop(0))

 

    while slist1:

        result.append(slist1.pop(0))

 

    while slist2:

        result.append(slist2.pop(0))

 

    return result

 

위에서 만들 정렬 함수를 호출해봅니다. 

 

소스 코드

li = [1,654,8,88,5,47,6,3,154,86,26,7]

print(merge_sort(li))

 

결과

[1, 3, 5, 6, 7, 8, 26, 47, 86, 88, 154, 654]

병합 정렬에 대해서 알아봤습니다.