병합 정렬(Merge Sort) - 파이썬 코드 구현

Merge sort python code implementation
merge sort 파이썬 코드를 작성해 보자.

---

병합 정렬(Merge Sort)

위키피디아의 설명을 참고해 보자.

병합 정렬은 다음과 같이 작동한다.

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

병합 정렬의 핵심은, 문제를 푸는 방법론을 사이즈를 반으로 쪼갠 녀석에 적용해서 정렬을 완료한 후, 정렬이 완료된 반쪽짜리 2개를 다시 합침으로써 정렬을 마친다는 것이다.

즉, merge_sort함수는 2개의 merge_sort(사이즈는 반)를 재귀적으로 호출한 후, 재귀적으로 호출한 결과값을 받아 이 둘을 합치는(merge 함수)로 구성된다.

간단한 수도코드를 쓰면 다음과 같다.

merge_sort(A, p, r)
    q = (p+r)/2
    merge_sort(A, p, q)
    merge_sort(A, q+1, r)
    merge(A, p, q, r)

이때 A는 배열, p는 시작 인덱스, r은 끝 인덱스를 의미한다. q는 중간값으로, merge_sort를 재귀적으로 쪼개서 호출할 때의 경계가 된다.

마지막으로 merge함수는 쪼개진 두 배열을 첫항부터 차례로 비교한 후, 작은 녀석부터 순서에 맞게 정렬을 해 준다. 항을 하나하나 비교하는 것 밖에 수행하지 않으므로, 최대 비교 횟수는 (쪼개진 두 배열의 각 길이의 합 - 1)이 될 것이다.

예시를 통해 merge함수가 어떻게 작동하는지 알아보자.

위 그림은 총 길이 10개짜리 배열을 길이 5짜리 배열 2개로 나누어 합병이 이루어지는 과정을 보여주고 있다.

이때, temp라는 배열이 추가로 필요한데, 이는 비교한 값들을 기존 배열에 바로 대입시킬 수 없기 때문이다. 따라서 병합 정렬은 추가적인 공간 n만큼을 필요로 한다. (n = r - p + 1, 기존 배열의 길이만큼)

이제 파이썬 코드를 짜보도록 하자.

# Merge sort implementation
import sys #for sys.maxsize
import copy # for merge sort, addtional space

array1 = [4,3,9,1,5,6,7,22,3243,436,56,4,73,45,24,23,5]
array2 = [100]


#
# Helper functions
#
# swap, print_array
#

def swap(array, a, b):
    array[a], array[b] = array[b], array[a]

def print_array(input):
    for i in range(len(input)):
        print(input[i], end=' ')
    print()    

#
# Main sorting function : 
#

def merge_sort(arr, p, r):
    q = int((p+r)/2)
    if p+1 <= r:
        merge_sort(arr, p, q)
        merge_sort(arr, q+1, r)
        return merge(arr, p, q, r)
    else:
        return arr

def merge(arr, p, q, r):
    i, j, t = p, q+1, 0
    temp = [0] * (r-p+1)
    # Compare each array, when index is not out of bound
    while i <= q and j <= r:
        if arr[i] < arr[j]:
            temp[t] = arr[i]
            t += 1
            i += 1
        else:
            temp[t] = arr[j]
            t += 1
            j += 1
    # When one of the index is out of bound, just add them
    while i <= q:
        temp[t] = arr[i]
        t += 1
        i += 1
        if i > q: break
    while j <= r:
        temp[t] = arr[j]
        t += 1
        j += 1
        if j > r: break

    for x in range(r-p+1):
        arr[p+x] = temp[x]

    return arr



### Test

print_array(array1)

array3 = merge_sort(array1, 0, len(array1)-1)

print_array(array3)