Merge Sort(병합 정렬)

MergeSort

• 일반적인 방법으로 구현했을 때, 이 정렬은 안정 정렬에 속하며, 분할 정복 알고리즘의 하나 이다.

과정

• 리스트의 길이가 0 또는 1이면 이미 정렬된 것으로 본다. 그렇지 않은 경우에는 정렬되지 않은 리스트를 절반으로 잘라 비슷한 크기의 두 부분 리스트로 나눈다
• 각 부분 리스트를 재귀적으로 병합 정렬을 이용해 정렬한다.
• 두 부분 리스트를 다시 하나의 정렬된 리스트로 병합한다.

Python 코드

from typing import MutableSequence



# 병합 정렬
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))
if __name__ =='__main__':
    print('병합 정렬을 수행합니다.')
    num = int(input('원소 수를 입력하세요.: '))
    x = [None]*num                  # 원소 수가 num인 배열을 생성
    
    for l in range(num):
        x[l] = int(input(f'x[{l}]: '))
    
    merge_sort(x)                   # 배열 x를 병합 정렬
    
    print('오름차순으로 정렬했습니다.')
    
    for l in range(num):
        print(f'x[{l}] = {x[l]}')

단점

• 만약 배열로 구성하면, 임시 배열이 필요하다
• 정렬하려는 데이터의 크기가 큰 경우, 이동 횟수가 많아 큰 시간적 낭비를 초래할 수 있다

장점

• 안정적인 정렬 방법
• 데이터 분포에 영향을 덜 받는다(QuickSort와 달리) 입력 데이터가 무엇이든 간에 정렬되는 시간은 O(nolog2n)으로 동일하다.
• 만약 데이터를 LinkedList로 구성한다면, 링크 인덱스만 변경되므로 데이터의 이동은 무시할 수 있을 정도로 작아진다.
• 따라서 크기가 큰 데이터를 정렬할 때, LinkedList를 사용한다면 MergeSort는 QuickSort를 포함한 다른 어떤 정렬보다 효율적이다.

시간 복잡도