[정렬 알고리즘] - Merge Sort

Merge sort

하나의 리스트를 두개의 균등한 크기로 분할하고 분할된 부분 리스트를 정렬한 다음, 두 개의 정렬된 부분 리스트를 병합하여 전체가 정렬된 리스트가 되게 하는 정렬 방법이다. 합병 정렬은 분할 정복(Devide and conquer) 방법에 바탕을 두고 있다.

 

1. 분할(Devide) : 정렬하려는 리스트를 같은 크기의 2개의 부분 배열로 분할한다.
2. 정복(Conquer) : 부분 배열을 정렬한다. 부분 배열의 크기가 충분히 작을때까지 재귀 호출을 이용하여 1단계-2단계를 반복한다.
3. 결합(Combine) : 정렬된 부분 배열들을 하나의 배열로 합병한다.

이해를 돕기 위한 애니메이션 영상!!

구현

(업로드 예정입니다!!)

def merge(leftList, rightList):
    i = 0
    j = 0
    sorted_list = []
    while(i<len(leftList) and j<len(rightList)):
        if leftList[i] < rightList[j]:
            sorted_list.append(leftList[i])
            i+=1
        else:
            sorted_list.append(rightList[j])
            j+=1

    #남은값들 다 넣어주기
    while(i<len(leftList)):
        sorted_list.append(leftList[i])
        i+=1
    while(j<len(rightList)):
        sorted_list.append(rightList[j])
        j+=1
    return sorted_list
        

def mergeSort(origin):
    # base case
    if len(origin) <= 1:
        return origin
    
    mid = len(origin) // 2
    leftList = origin[:mid]
    rightList = origin[mid:]

    leftList = mergeSort(leftList)
    rightList = mergeSort(rightList)
    return merge(leftList, rightList)

print(mergeSort([14, 7, 3, 12, 9, 11, 6, 2]))

시간 복잡도 분석

예를 들어, 리스트의 크기가 N($2^3)$일때 순환 호출의 깊이 k 는 $log_2N$($log_23$)이 된다. ($n = 2^k$)

배열이 부분배열로 나눠질때는 인덱스를 기준으로 단순하기 나누기 때문에 부분 배열이 합쳐지는 결합단계에서 시간 복잡도를 체크하면된다.

하나의 합병 단계에서 최대 n번의 비교 연산이 필요하다. 결과적으로 merge 단계가 $log_2N$만큼 있고 원소의 크기를 비교하는 비교 연산이 최대 N번 있을수있기 때문에 $Nlog_2N$ 번 필요하다.

합병 정렬의 장점은 안정적인 정렬 방법으로 데이터의 분포에 영향을 덜 받는다. 즉 입력 데이터가 무엇이든 간에 정렬되는 시간이 동일하다. 최악,평균,최선의 경우가 모두 $O(Nlog_2N)$ 이다.

참고

합병 정렬을 생성할때 임시 배열을 생성하여 부분 배열을 저장한다. 또한 레코드의 크기가 클 경우 이동 횟수가 많을수있다. 이때 각각의 레코드를 연결리스트로 구성하여 합병 정렬을 하면 연결리스트 각각이 가리키는 포인터(링크 인덱스)가 달라지기 때문에 퀵정렬을 포함하여 다른 어떤 정렬 방법보다도 효율적일 수 있다.