[python] 합병 정렬(Merge sort)

합병 정렬

• 하나의 리스트를 두 개의 균등한 크기로 분할하고 분할된 부분 리스트를 정렬한 다음, 두 개의 정렬된 부분 리스트를 합하여 전체가 정렬된 리스트를 얻는다.
• 분할 정복(divide and conquer) 기법에 바탕을 두고 있는 정렬이다.
• 즉 하나의 리스트를 2개의 작은 문제로 분리하고 각각을 해결한 다음, 결과를 모아서 원래의 문제를 해결한다. 분리된 문제가 해결되지 않는다면 분할 정복 문제를 반복하여 적용한다. (순환 호출)
• 합병 정렬 단계
  1. 분할(Divide): 입력 배열을 같은 크기의 2개의 부분 배열로 분할한다.
  2. 정복(Conquer): 부분 배열을 정렬한다. 부분 배열의 크기가 충분히 작지 않으면 순환 호출을 이용하여 다시 분할 정복 기법을 적용한다.
  3. 결합(Combine): 정렬된 부분 배열들을 하나의 배열에 통합한다.

 

합병 정렬의 과정

• 8 리스트를 4/4 > 2/2/2/2 >1/1/1/1/1/1/1/1 로 Divide 한다.
• 1/1 을 Conquer하고 Combine을 하여 {27}, {10}을 {10, 27}로, {12},{20}을 {20,21}로 만든다.
• 2/2 를 위와 같은 방법으로 {10, 27}, {20,21}을 {10,12,20,27}로 만든다.
• 마지막 4/4를 처음과 같은 8 리스트로 정렬, 결합하여 만든다.

 

실제 리스트를 합하는 과정

• 2개의 리스트의 요소들을 처음부터 하나씩 비교하여 두개의 리스트 요소 중에서 더 작은 요소를 새로운 리스트로 옮긴다.
• 두 개의 리스트 중 하나가 끝날 때 까지 이 과정을 되풀이한다.
• 만약 둘 중에서 하나의 리스트가 먼저 끝나게 되면 나머지 리스트의 요소들을 전부 새로운 리스트로 복사한다.

 

합병 알고리즘 특징

• 합병 정렬은 순환 호출 구조로 되어있어서 순환 호출의 깊이는 k=log2 * n 이다.
  • 레코드의 개수 n이 2의 거듭 제곱이라고 가정하고 n = 2^3인 경우 부분 배열의 크기가 2^3 -> 2^2 -> 2^1 -> 2^0순으로 줄어든다.
  • 따라서 일반적으로 n=2^k라고 하면 부분 배열의 크기는 2^k -> 2^k-2 -> ... 2^0이 되어 순환 호출의 깊이가 k가 될 것이다.
• 하나의 합병 단계에서는 최대 n번의 비교 연산이 필요하다. 이러한 합병 단계가 k=log2 * n 번 만큼 있으므로 총 비교 연산은 최대 n * log2 * n 번 필요하다.
• 이동 연산의 경우 총 부분 배열에 들어 있는 요소의 개수가 n인 경우, 레코드의 이동이 2n번 발생하므로 하나의 합병 단계에서 2n개가 필요하다. 따라서 log2n개의 합병 단계가 필요하므로 총 2n * log2n개의 이동 연산이 필요하다.
• 즉 합병 정렬은 비교 연산과 이동 연산의 경우 O(nlog2n)의 복잡도를 가진다.

 

코드 정리

# 병합 정렬
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
  
# 최적화
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))
  
  # 출처 - https://www.daleseo.com/sort-merge/