#05 병합 정렬(Merge Sort)

합병 정렬이라고도 부르며, 분할 정복 방법을 통해 구현

퀵 정렬과는 다르게 안정 정렬에 속함

시간 복잡도는 최악, 평균, 최선 모두 O(nlogn)이며 공간 복잡도는 O(2n)이다. 입력값을 제외하면 O(n)

 

Average Case

Worst case (Reverse List)

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:])
    
    merge_arr = []
    l, h = 0, 0

    while l < len(low_arr) and h < len(high_arr):
        if low_arr[l] < high_arr[h]:
            merge_arr.append(low_arr[l])
            l += 1
        else:
            merge_arr.append(high_arr[h])
            h += 1
    
    merge_arr += low_arr[l:] + high_arr[h:]
    return merge_arr

def improved_merge_sort(arr):
    # 1. 주어진 배열을 쪼갤 수 있을 때 까지 쪼갬 O(logn)
    # 2. 원소 값을 비교하며 병합하며 합침
    def sort(low,high):
        if high - low < 2 :
            return
        mid = (high + low) // 2
        sort(low,mid)
        sort(mid,high)
        merge(low,mid,high)

    def merge(low,mid,high):
        # 원소값을 비교 O(n)
        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))

위의 방법 같은 경우는 slicing을 활용해서(부분 배열) 메모리 사용효율이 좋지 않다.

간단하게 계산하면 100개의 입력이 들어온다고 하면, 50개 만큼 복사 -> 그 50개 중 또 25개 복사 -> 12개 복사 -> 6개...

 

메모리 효율을 올리기 위해 하단 함수를 구현할 수 있다.

리스트 인덱스를 기반으로 in - place sort로 구현하면 된다.

 

수행 시간 비교

공간 효율을 늘려서 약간의 시간차가 있다. 역시 시간과 공간은 trade - off 관계인 것 같다.

 

참고 :

https://codepumpkin.com/merge-sort-sorting-algorithm/

https://www.daleseo.com/sort-merge/