[Algorithm] Merge Sort (병합 정렬)

0. Merge Sort (병합 정렬) 이란?

 

병합 정렬이란, 배열을 쪼개서 정렬한 후 다시 그 쪼개진 배열들을 정렬하며 합치는 것을 말한다.

예를 들어, [1, 3, 5, 2] 이라는 배열이 있다고 하자. 

이 배열을 반으로 쪼개면 [1, 3], [5, 2] 이 될 것이다.

이들을 각각 정렬하면 [1, 3], [2, 5] 가 된다. 

이들을 합치며 정렬한다는 것은, 각각의 원소를 비교하여 작은 것부터 새 배열에 입력하는 것이다.

1 < 2 이므로 1이 맨 첫번째, 3 > 2 이므로 2가 두번째, 3 < 5 이므로 3이 세번째, 마지막에 5가 입력될 것이다.

 

이를 어떻게 코드로 구현할 수 있을까? 지금 든 예제는 4개여서 반으로 갈라 정렬하는 것이 쉬웠지만, 실제로는 그렇지 않다.

따라서 배열의 원소가 하나가 될 때까지 쪼갠 뒤, 이들을 합치는 것을 반복한다. 

배열의 원소가 하나가 될 때까지 쪼갠다는 것은 쪼개는 것을 '재귀적으로' 반복하는 것이다. 

따라서 재귀함수를 이용한다.

 

여기서 쪼개는 과정과 / 합치는 과정 두 가지로 나누어지는 것을 볼 수 있다. 

따라서 두 개의 함수가 필요하다.

배열의 길이를 N이라고 하면, N/2, N/4, ... , 1개가 될 때까지 쪼갠 뒤, 1개가 되면 배열을 반환한다.

이후 합치는 과정을 반복한다.

 

합치는 과정은 두 배열의 원소를 모두 비교해야 한다. 그러나 두 배열은 정렬되었다는 가정 하에 합치는 과정이 이루어지기 때문에, 두 배열을 다 앞에서부터 비교하며 작은 것을 새 배열에 넣는다. (예제 참고) 이후 새 배열을 반환하고, 새 배열들을 다시 합치는 과정을 반복한다.

 

1. 구현

 

def merge(num, low, mid, high):
    merged_num = []
    i = low
    j = mid + 1
    k = low

    while i <= mid and j <= high:
        if num[i] < num[j]:
            merged_num.append(num[i])
            i += 1
        else:
            merged_num.append(num[j])
            j += 1
    while i <= mid:
        merged_num.append(num[i])
        i += 1
    while j <= high:
        merged_num.append(num[j])
        j += 1

    idx = 0
    for iter in range(low, high+1):
        num[iter] = merged_num[idx]
        idx += 1

    return merged_num

def merge_sort(num, low, high):
    if low < high:
        mid = int((low + high) / 2)
        merge_sort(num, low, mid)
        merge_sort(num, mid + 1, high)
        merge(num, low, mid, high)

n = int(input())
nums = input()
num = nums.split()

for i in range(n):
    num[i] = (int)(num[i])

merge_sort(num, 0, n-1)

for i in range(n):
    print(num[i], end=' ')

1)merge

쪼개진 두 배열을 합치는 과정이다. 입력된 배열은 원래 배열의 low-mid, mid-high+1이다. 단, 같은 배열 내에 있으므로 굳이 두 개로 쪼개어 시간을 늘리지 않고, index로 두 배열을 구분한다. 

 

i를 첫 번째 배열의 현재 index, j를 두 번째 배열의 현재 index로 초기화한다 (low, mid+1).

이후 i와 j를 비교하여 작은 것을 새로운 배열에 넣고, 선택된 쪽의 index를 늘린다. 이 과정을 반복하면 두 배열의 길이가 같다면 새로운 배열에 정렬이 완료되었을 것이다.

 

그러나 원소의 갯수가 홀수인 배열을 쪼개면 두 배열의 길이는 달라질 것이다.

작은 배열은 이미 다 들어갔을 것이기 때문에, i와 j 중 둘 중 하나는 각 배열의 끝 index를 가리킬 것이다.

그러나 그것이 무엇인지 알 방법은 없기 때문에 (알 수는 있지만 굳이 비교 연산을 추가하지 않기 위해), 둘 다 끝 index로 갈 때까지 남은 원소들을 새로운 배열에 넣어준다. 남은 원소들은 정렬된 배열에 있는 것보다 큰 것이면서 남은 배열 내에서 정렬된 상태이기 때문에 그냥 index를 하나씩 늘려가며 넣어주면 된다.

 

2) merge_sort

low < high 조건을 걸지 않으면 배열의 쪼개기가 무한대로 이루어져 정상적인 답을 얻을 수 없다. low=high 일 때는 배열에 원소가 하나만 있을 때이므로 고려할 필요가 없다. 

위 조건을 만족하면, low-mid까지의 정렬, mid+1-high까지의 정렬을 완료한 뒤 둘을 합쳐준다. 재귀적인 구조로 되어있기 때문에 원소가 두 개일 때부터 모든 원소가 정렬될때까지 이 과정을 반복할 것이다.

 

3) 실행

low는 0, high는 n-1로 설정한다. index(i or j)<=high라는 조건문이 있기 때문에, 배열의 맨 마지막까지 고려하려면 실제 index인 n-1을 넣어줘야 한다.