[알고리즘] 정렬 알고리즘 : 합병정렬 (Merge sort)

정렬의 기초로 분할 정복 방법을 사용해 분할, 정복, 결합의 세 단계를 거친다.

• 분할: 배열을 동일한 크기의 두 개의 부분 배열로 분할한다. 입력 크기를 n이라고 한다면 분할된 부분배열의 크기는 n/2가 된다.
• 정복: 각각의 부분 배열에 대해 합병 정렬을 순환적으로 적용한다.
• 결합: 정렬된 두 부분 배열을 합쳐서 하나의 정렬된 배열을 만든다.

간단하게 설명하면 합병정렬은 배열을 쪼개서 각각 정렬한 후 합치는 알고리즘이다.

def merge_sort(num):
    l = len(num)
    if l > 1:
        mid = round(l/2+0.1)
        left = merge_sort(num[:mid])
        right = merge_sort(num[mid:])
        num = merge(left, right, mid, l-mid)
    return num

def merge(left, right, l_left, l_right):
    i=j=0
    li = []
    while i < l_left and j < l_right:
        if left[i] <= right[j]:
            li.append(left[i])
            i+=1
        else:
            li.append(right[j])
            j+=1
    if i < l_left:
        li = li + left[i:]
    elif j < l_right:
        li = li + right[j:]
    return li

코드를 보면 다섯 번째, 여섯 번째 줄에서 merge_sort함수를 순환적으로 호출해서 left, right배열에 원소가 하나씩만 남을 때까지 배열을 반으로 쪼갠다. 하나가 되면, merge함수가 실행되어 각 원소 값을 비교하여 정렬된 하나의 새로운 배열로 만든다. 이 과정을 순환적으로 반복하여 전체 배열을 정렬한다.

 

예를 들어 [9,6,3,4]이라는 배열이 입력되었다고 할 때, 첫 번째 호출에서 merge_sort([9,6])이 들어가서 left = merge_sort([9])를 한번 더 호출한다. 이는 배열의 길이가 1이므로 그대로 [9]가 리턴되어 left = [9]가 된다.

 right도 마찬가지로 [6]이 할당되고, 그 다음 merge함수가 호출되어 [9]와 [6]의 원소값을 비교하여 li에 할당한다. 6이 9보다 작으므로 li에는 6이 들어가고 else문에서 j는 1을 더해주었으므로 j = 1 = l_right( 오른쪽 배열의 길이값)이 되지만 i에는 아무런 작업도 해주지 않았으므로 while문을 빠져나간 후 if문에 걸려 li에 left의 배열을 더해주게 된다. 따라서 li는 [6] + [9]가 되어 merge함수의 리턴 값, 즉 merge_sort([9,6])의 리턴값은 [6,9]가 된다.

 right는 merge_sort([3,4])값인데, 위와 동일한 과정을 반복하여 [3,4]값을 얻게된다. 그 후 merge함수를 최종적으로 호출하여 [6,9]와 [3,4]의 원소를 하나씩 비교하여 정렬한다.

 

단점

 위의 [3,4]의 케이스에서 보면 알 수 있듯, 이미 정렬된 배열도 모두 비교 연산을 수행한다.

 

복잡도 및 특징

원소를 하나씩 순서대로 비교하므로 안정적 정렬이다. 

TS: O(n)

 지나가다가 합병정렬을 제자리 정렬로 구현했다는 코드를 본 것 같은데 기본적으로 합병정렬은 제자리 정렬이 아니다. 제자리 정렬 할 수 있는 코드를 알아낸다면 추가로 포스팅 해야지...

 TC: O(nlogn)

 분할에 logn, 비교병합에 n의 시간복잡도가 소요된다.

적용 가능한 문제

 합병정렬을 그대로 사용하는 문제는 많이 없는 것 같고, "왼쪽부터" O(nlogn)시간 내에 정렬을 수행한다는 특징을 차용하여 변형한 풀이들이 있는 것 같다.