[정렬] merge sort

divide&conquer 방식의 알고리즘으로서 일반적으로 재귀 호출을 통해서 구현된다.

과정은 다음과 같다.

 

1. 리스트의 길이가 1 이하이면 이미 정렬된 리스트이다.

2. 정렬되지 않은 리스트를 동일한 또는 비슷한 크기의 두 개의 부분 리스트로 분할한다. (divide)

3. 각 부분 리스트를 재귀적으로 merge sort를 이용하여 정렬한다. (conquer)

4. 두 부분 리스트를 하나의 리스트로 병합한다. (combine)

 

[5, 2, 4, 7, 6, 1, 3, 8]

[5, 2, 4, 7] / [6, 1, 3, 8]

[5, 2] / [4, 7] // [6, 1] / [3, 8]

[5] / [2] // [4] / [7] /// [6] / [1] // [3] / [8] ↑divide ↓conquer, combine

[5, 2] / [4, 7] // [1, 6] / [3, 8]

[2, 4, 5, 7] / [1, 3, 6, 8]

[1, 2, 3, 4, 5, 6, 7, 8]

 

여기서 merge의 과정은 A=[2, 4, 7, 9]과 B=[1, 3, 5, 6]을 예로 들어 살펴보자.

i는 리스트 A에 대한 인덱스이고, j는 리스트 B에 대한 인덱스이다.

 

1. i=0, j=0 / A[0]과 B[0]을 비교하여 보다 작은 B[0]을 배열에 삽입.

A = [2, 4, 7, 9]

B = [1, 3, 5, 6]

 

2. i=0, j=1 / A[0]과 B[1]을 비교하여 보다 작은 A[0]을 배열에 삽입.

A = [2, 4, 7, 9]

B = [1, 3, 5, 6]

 

3. i=1, j=1 / A[1]과 B[1]을 비교하여 보다 작은 B[1]을 배열에 삽입.

A = [2, 4, 7, 9]

B = [1, 3, 5, 6]

 

4. i=1, j=2 / A[1]과 B[2]를 비교하여 보다 작은 A[1]을 배열에 삽입.

A = [2, 4, 8, 9]

B = [1, 3, 5, 6]

 

5. i=2, j=2 / A[2]와 B[2]를 비교하여 보다 작은 B[2]를 배열에 삽입.

 

6. i=2, j=3 / A[2]와 B[3]를 비교하여 보다 작은 B[3]을 배열에 삽입.

 

7. i=2, j=4 / B에 더 이상 비교할 원소가 없고, 이 때 A는 이미 정렬되어 있는 상태이므로 A[i]부터 차례대로 배열에 삽입.

A[3] 삽입.

 

시간복잡도

반드시 i, j 중 하나 이상은 1 이상씩 증가하면서 merge가 이루어지기에 정렬에 n만큼 소요되고,

리스트를 c개씩 분할했을 때, 이러한 과정이 log_c(n)만큼 발생하므로 O(nlog(n))이다.

 

특징

연결리스트로 구현함으로써 in-place-sort가 가능하다.

원래 리스트에서 앞에 있던 원소는 순서가 있는 다른 분할된 배열에 있거나,

또는 같은 부분 배열 안에 있더라도 위치가 바뀌지 않으므로 stable sort이다.

 

def merge(left, right):
    res = []
    i, j = 0, 0
    while(i<len(left) and j<len(right)):
        if left[i]<right[j]:
            res.append(left[i])
            i += 1
        else:
            res.append(right[j])
            j += 1
    while(i<len(left)):
        res.append(left[i])
        i += 1
    while(j<len(right)):
        res.append(right[j])
        j += 1

    return res

def merge_sort(arr):
    ### 리스트의 길이가 1 이하일 때, 이미 정렬이 완료된 것이다.
    if len(arr) <= 1: return arr

	### left, right로 분할한 후,
    ### 각각에 대해 merge sort을 시행하고,
    ### 그 후 merge한다.
    mid = len(arr) // 2
	
    left_arr = arr[:mid]
    right_arr = arr[mid:]
    left_arr = merge_sort(left_arr)
    right_arr = merge_sort(right_arr)

    return merge(left_arr, right_arr)



arr = [7, 2, 10, 21, 13, 14, 5, 18, 35, 9, 1, 2]
print(merge_sort(arr)) # [1, 2, 2, 5, 7, 9, 10, 13, 14, 18, 21, 35]