[알고리즘] 5) 병합 정렬 알고리즘

병합 정렬 알고리즘도 대표적인 '분할 정복' 방법을 채택한 알고리즘. 

퀵정렬과 동일하게 O(NlogN)의 시간복잡도를 가진다. 

주어진 원소를 원소 하나만 남을 때까지 쪼갠 후에 다시 크기 순으로 재배열하면서 원래 크기의 배열로 합친다. 

 

아래 리스트가 있다고 가정해보자.

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

각 원소마다 하나의 리스트가 생기도록 쪼갠 후에 역으로 두개씩 합치는 과정을 시작한다. 

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

합칠때는 작은 숫자가 앞에 오도록 위치, 이후 각각 2개의 배열을 하나의 배열로 합치는 작업을 수행한다. 

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

두개의 인자중 작은 인자부터 하나씩 비교하기 시작하면 작은 값부터 차례대로 배열을 정리할 수 있다. 

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

파이썬 구현

def merge_sort(arr):
    if len(arr) < 2:
        return arr

    mid = len(arr) // 2
    low_arr = merge_sort(arr[:mid])
    high_arr = merge_sort(arr[mid:])

    merged_arr = [] # 새로운 배열을 매번 생성 -> 메모리 사용량에 영향을 준다는 단점.
    l = h = 0
    while l < len(low_arr) and h < len(high_arr):
        if low_arr[l] < high_arr[h]:
            merged_arr.append(low_arr[l])
            l += 1
        else:
            merged_arr.append(high_arr[h])
            h += 1
    merged_arr += low_arr[l:]
    merged_arr += high_arr[h:]
    return merged_arr

[최적화]

병합 결과를 담을 새로운 배열을 매번 생성해서 리턴하지 않고, 인덱스 접근을 이용해 입력 배열을 계속해서 업데이트하면 메모리 사용량을 대폭 줄일 수 있다. (In-place sort) 

• sort와 merge의 분리 구현

def merge_sort(arr):
    def sort(low, high):
        if high - low < 2:
            return
        mid = (low + high) // 2
        sort(low, mid)
        sort(mid, high)
        merge(low, mid, high)

    def merge(low, mid, high):
        temp = []
        l, h = low, mid

        while l < mid and h < high:
            if arr[l] < arr[h]:
                temp.append(arr[l])
                l += 1
            else:
                temp.append(arr[h])
                h += 1

        while l < mid:
            temp.append(arr[l])
            l += 1
        while h < high:
            temp.append(arr[h])
            h += 1

        for i in range(low, high):
            arr[i] = temp[i - low]

    return sort(0, len(arr))