파이썬의 자료구조 - 합병 정렬

앞에서 여러가지의 정렬을 알아보았는데 그 중 합병 정렬을 다뤄보겠다.

합병 정렬(Merge Sort)이란?

입력이 2개의 부분 문제로 분할되고, 부분 문제의 크기가 1/2로 감소하는 분할 정복 알고리즘
즉, n개의 숫자들을 n/2개씩 2개의 부분문제로 분할하고, 각각의 부분 문제를 순환적으로 합병 정렬한 후, 2개의 정렬된 부분을 합병하여 정렬하는 것.
이를 이용하여 합병 과정이 정복하는 것이라고 할 수 있다. 여기서 합병이란 2개의 각각 정렬된 숫자들을 1개의 정렬된 숫자들로 합치는 것이다.

합병 정렬의 과정

그림을 통해 합병 정렬 수행 과정을 알아보자.
맨 위에 원소의 개수가 8인 정렬되지 않은 배열이 있다. 저 배열을 정렬하기 위한 방법은 반으로 나누어 다시 합병정렬을 하는 것이다.
원소의 개수가 4 -> 2 -> 1 로 될때까지 반으로 나눈다.

이제 원소의 개수가 1이 되었으면 배열을 다시 합병(정복)해주면 된다.
두 원소의 크기를 비교해 작은 것부터 임시 배열에 넣고 (오름차순) 이 과정을 반복하면서 배열을 합치면서 병합한다.
왼쪽과 오른쪽을 정렬했다면, 이제 왼쪽 배열과 오른쪽 배열의 원소를 하나하나 비교해 작은 것부터 다시 넣는다.

마지막 과정을 한번 본다면 <원소의 개수 8> 일 때의 왼쪽 배열을 정렬한 것을 알 수 있다.
이제 <원소의 개수 8> 일 때의 오른쪽 배열(35, 13, 25, 24))도 위와 같은 과정을 거쳐 아래와 같이 정렬된다면,
이 왼쪽 배열(10, 22, 30, 37)과 비교해서 배열을 완성하게 된다.

이를 통해 병합 정렬을 마무리하였다.

한 마디로 요약하자면, 정렬되지 않은 배열을 받으면 그냥 원소의 개수가 1이 될 때까지 반으로 계속 나누다가, 원소의 개수가 1이 된다면 그때부터 나눠왔던 원소들의 값을 비교해서 합치는 것이다.

코드 구현

python을 이용하여 병합 정렬을 구현해보았다.

import sys
input = sys.stdin.readline
result = 0

def merge(s,e) : # s(시작),e(종료),m(중간)
    global result 
    if e - s < 1 :
        return
    m = int(s + (e-s) / 2)
    merge(s,m) # 재귀 함수로 리스트 나누기
    merge(m+1, e)
    for i in range(s, e+1):
        temp[i] = A[i] # 임시로 리스트 저장
    k = s
    
    # 두 그룹 나누고 병합하는 방식
    index1 = s
    index2 = m+1
    while index1 <= m and index2 <= e: # 양쪽의 인덱스를 비교하여 더 작은 수를 선택후 리스트에 저장
        if temp[index1] > temp[index2] :
            A[k] = temp[index2]
            result = result + index2 - k # 뒤쪽 데이터값이 더 작으면 결과값 업데이트
            k += 1
            index2 += 1 # 선택한 데이터 index값을 오른쪽으로 이동
        else :
            A[k] = temp[index1]
            k += 1
            index1 += 1
    while index1 <= m :
        A[k] = temp[index1]
        k += 1
        index1 += 1
    while index2 <= e :
        A[k] = temp[index2]
        k += 1
        index2 += 1

N = int(input())
A = list(map(int,input().split()))
A.insert(0, 0)
temp = [0] * int(N+1)
merge(1,N)
print(result)