알고리즘 | 정렬 기법 | 병합 정렬(Merge Sort)

Merge Sort는 이전 포스팅에서 공부했던 Quick Sort와 함께 분할 정복을 활용한 대표적인 정렬 기법이다. 

1945년에 폰 노이만이 개발했다고 한다. 

 

안정적인 정렬로 알려져 있으며, 데이터의 크기와 상관없이 일정한 성능을 보여준다는 장점이 있다. 따라서 대용량의 데이터를 정렬할 때 효과적이라고 한다.

 

앞서 Quick Sort가 Java에서 기본형 타입의 배열의 Array.sort() 메서드에 활용된다고 했는데, 객체 타입 배열의 Array.sort()에는 Tim Sort가 쓰인다. 파이썬의 list.sort()와 sorted(list)도 Tim Sort 기반으로 동작한다. 

 

여기서 Tim Sort가 삽입 정렬(Insertion Sort)과 Merge Sort를 결합한 기법이다. 

 

---

1. 핵심 아이디어

Merge Sort의 핵심 아이디어는 분할 정복 알고리즘의 핵심 아이디어와 동일하다. 

n개의 인덱스를 가진 배열이 주어졌을 때, 

1. 분할 (Divide): 주어진 배열을 가장 작은 부분 배열이 될 때까지 반으로 계속 나눈다. 즉, 부분 배열의 원소가 0개 혹은 1개가 되면 1번 과정은 끝나고 2번으로 넘어간다. 

2. 정복(Conquer): 각 부분 배열을 재귀적으로 병합 정렬한다.
-> 가장 작은 부분 배열부터 '3. 병합 (Merge)' 과정을 수행하며 최초 크기의 배열까지 올라온다. 

3. 병합 (Merge): 양쪽의 배열(left, right)을 정렬하면서 합친다. 

내 생각에는 '2. 정복 (Conquer)'과 '3. 병합 (Merge)' 부분을 이해하는 것이 핵심인 것 같다. 

- Merge는 양쪽 배열을 그냥 합치는 게 아니라, 정렬하면서 합치는 것임을 명심해야 한다. 

 

출처: https://www.101computing.net/merge-sort-algorithm/

 

2. 코드를 통한 이해

위 1, 2, 3번 과정을 재귀적으로 구현하면 된다. 

Quick Sort를 공부할 때와 마찬가지로 백준 2750번 문제(수 정렬하기)를 통해 연습하였다. (https://www.acmicpc.net/problem/2750)

 

# 머지 소트 구현해보기

'''
1. 분할 (Divide): 주어진 배열을 가장 작은 부분 배열이 될 때까지 반으로 계속 나눈다. 
    즉, 부분 배열의 원소가 0개 혹은 1개가 되면 1번 과정은 끝나고 2번으로 넘어간다. 

2. 정복(Conquer): 각 부분 배열을 재귀적으로 병합 정렬한다.
-> 가장 작은 부분 배열부터 '3. 병합 (Merge)' 과정을 수행하며 최초 크기의 배열까지 올라온다. 

3. 병합 (Merge): 양쪽의 배열(left, right)을 정렬하면서 합친다. 
'''

# Merge Sort 전체를 수행하는 함수
def merge_sort(arr):
    # base case: 배열의 길이가 1 이하라면 반환
    if len(arr) <= 1:
        return arr
    
    # 1. 분할 (Divide) - 가운데 인덱스를 기준으로 양분하기    
    mid = len(arr)//2
    left = arr[:mid]
    right = arr[mid:]
    
    # 2. 정복
    left = merge_sort(left)
    right = merge_sort(right)

    # 3. 결합: 두 부분 배열을 merge
    return merge(left, right)
    

# Merge Sort 내부의 '3. 병합' 과정을 수행하는 함수
def merge(left, right):
    result = []
    i = j = 0 # i와 j는 각각 left와 right 배열의 인덱스

    # left와 right의 원소를 비교하며 result에 추가
    while i < len(left) and j < len(right): # 둘 중 하나가 빌 때까지
        # 더 작은 순서대로 임시 배열(result)에 담기
        if left[i] < right[j]:
            result.append(left[i])
            i += 1 # 다음 인덱스로 이동
        else:
            result.append(right[j])
            j += 1 # 다음 인덱스로 이동

    # 남아 있는 원소들을 순서대로 result에 추가
    '''
    이때, left에 원소가 남았든 right에 남았든, 남아 있는 원소들은 반드시 result의 가장 큰 값보다 크다. 
    '''
    while i < len(left):
        result.append(left[i])
        i += 1
    
    while j < len(right):
        result.append(right[j])
        j += 1

    return result





### 문제 입력받는 부분 ###
arr = []
for i in range(int(input())):
    arr.append(int(input()))

### 문제 출력하는 부분 ### 
arr = merge_sort(arr)
for num in arr:
    print(num)

 

위 Merge Sort 구현 코드는 두 가지 함수로 구성된다. 

 

1. Merge Sort 전체를 수행하는 함수 (merge_sort)

2. Merge Sort 내부의 Merge 단계를 수행하는 함수 (merge)

 

처음에는 Merge()의 작동 메커니즘이 잘 이해되지 않았는데, left와 right가 정렬된 채로 올라온다는 걸 깨닫고 나니 이해가 수월했다.

 

 

3. 시간 복잡도

1. 최악의 경우: O(nlogn)
2. 평균 경우: O(nlogn)
3. 최선의 경우: O(nlogn)