병합 정렬

병합 정렬

병합 정렬은 분할 정복 기법으로 정렬하는 알고리즘으로, 하나의 배열을 중간을 기준으로 계속 나눠서 계속 합치면서 정렬하는 방법입니다. 퀵 정렬의 경우에는 최악의 경우(모두 정렬되어 있는 경우) $O(n^2)$의 시간복잡도를 가질 수 있지만 병합 정렬은 어떠한 배열에서도 $O(n\log_2 n)$의 시간복잡도를 가진다는 특징이 있습니다.

분할

Index	0	1	2	3	4	5	6	7
Value	5	2	1	3	6	9	7	4

위와 같은 배열이 있다고 가정하면, 병합 정렬은 먼저 분할의 과정을 거칩니다.

분할 #1

Index	0	1	2	3
Value	5	2	1	3

Index	4	5	6	7
Value	6	9	7	4

분할 #2

Index	0	1
Value	5	2

Index	2	3
Value	1	3

---

Index	4	5
Value	6	9

Index	6	7
Value	7	4

분할 #3

Index	0
Value	5

Index	1
Value	2

---

Index	2
Value	1

Index	3
Value	3

---

---

Index	4
Value	6

Index	5
Value	9

---

Index	6
Value	7

Index	7
Value	4

정복

분할 과정을 거쳤으니, 이제 배열을 정렬하여 합병하는 과정을 거칩니다. 이때 left, right 포인터와 정렬된 배열의 포인터를 하나 생성합니다. 이때 left 와 right 포인터를 사용해 왼쪽에 있는 배열의 left 번째 값이 오른쪽 배열의 right 값보다 크다면 right 를 증가시키고, 아니라면 right를 증가시켜서 저장합니다.

정복 #1

정복 #1 에서는 원소의 개수가 하나인 배열들을 정렬합니다. 다음 배열은 정렬된 결과가 저장될 배열입니다.

Index	0	1	2	3	4	5	6	7
Value
Pointer	k

인덱스 0, 1번을 정렬할 때 포인터는 left = 0(왼쪽 배열의 첫번째 인덱스) 이고, right = 1(오른쪽 배열의 첫번째 인덱스) 입니다. 정렬된 배열의 포인터 k는 left 입니다.

Index	0
Value	5
Pointer	left

Index	1
Value	2
Pointer	right

이때 첫번째 배열의 left 가 두번째 배열의 right 보다 작으므로, right를 하나 증가시키고 k번째에 right 값을 저장합니다. right 가 범위를 벗어나므로 종료합니다. 그러나 left 값이 저장되지 않았기 때문에 left 값 또한 저장해줍니다. 또한, k를 증가시킵니다.

Index	0	1	2	3	4	5	6	7
Value	2	5
Pointer			k

---

위의 과정을 반복하면,

Index	2
Value	1
Pointer	left

Index	3
Value	3
Pointer	right

Index	0	1	2	3	4	5	6	7
Value	2	5	1	3
Pointer					k

---

Index	4
Value	6
Pointer	left

Index	5
Value	9
Pointer	right

Index	0	1	2	3	4	5	6	7
Value	2	5	1	3	6	9
Pointer							k

---

Index	6
Value	7

Index	7
Value	4

Index	0	1	2	3	4	5	6	7
Value	2	5	1	3	6	9	4	7
Pointer

정복 #2

이제 원소가 두개씩 있는 배열들을 합병해야합니다. 이때 각각의 배열은 정렬되어있습니다. 똑같이 left, right, k 포인터를 사용합니다.

Index	0	1	2	3	4	5	6	7
Value
Pointer	k

Index	0	1
Value	2	5
Pointer	left

Index	2	3
Value	1	3
Pointer	right

이때 right 가 left보다 작으므로, right를 +1 하고, sorted에 저장합니다.

Index	0	1	2	3	4	5	6	7
Value	1
Pointer		k

Index	0	1
Value	2	5
Pointer	left

Index	2	3
Value	1	3
Pointer		right

이때 left 가 더 작으므로 left 를 +1 하고 sorted에 저장합니다.

Index	0	1	2	3	4	5	6	7
Value	1	2
Pointer			k

Index	0	1
Value	2	5
Pointer		left

Index	2	3
Value	1	3
Pointer		right

이때 right 가 더 작으므로 right +1 을 해주고 sorted에 저장합니다. 이때 right 가 범위를 벗어나므로 반복을 종료하고 남은 left 를 sorted에 저장합니다.

Index	0	1	2	3	4	5	6	7
Value	1	2	3	5
Pointer					k

---

Index	4	5
Value	6	9
Pointer	left

Index	6	7
Value	4	7
Pointer	right

이때 right 가 더 작으므로, right +1 을 해주고 sorted에 저장합니다.

Index	0	1	2	3	4	5	6	7
Value	1	2	3	5	4
Pointer						k

Index	4	5
Value	6	9
Pointer	left

Index	6	7
Value	4	7
Pointer		right

Index	0	1	2	3	4	5	6	7
Value	1	2	3	5	4	6
Pointer							k

Index	4	5
Value	6	9
Pointer		left

Index	6	7
Value	4	7
Pointer		right

Index	0	1	2	3	4	5	6	7
Value	1	2	3	5	4	6	7	9
Pointer

정복 #3

Index	0	1	2	3	4	5	6	7
Value
Pointer	k

Index	0	1	2	3
Value	1	2	3	5
Pointer	left

Index	4	5	6	7
Value	4	6	7	9
Pointer	right

위의 정복 과정을 반복하면,

Index	0	1	2	3	4	5	6	7
Value
Pointer	k

---

Index	0	1	2	3
Value	1	2	3	5
Pointer	left

Index	4	5	6	7
Value	4	6	7	9
Pointer	right

Index	0	1	2	3	4	5	6	7
Value	1
Pointer		k

---

Index	0	1	2	3
Value	1	2	3	5
Pointer		left

Index	4	5	6	7
Value	4	6	7	9
Pointer	right

Index	0	1	2	3	4	5	6	7
Value	1	2
Pointer			k

---

Index	0	1	2	3
Value	1	2	3	5
Pointer			left

Index	4	5	6	7
Value	4	6	7	9
Pointer	right

Index	0	1	2	3	4	5	6	7
Value	1	2	3
Pointer				k

---

Index	0	1	2	3
Value	1	2	3	5
Pointer				left

Index	4	5	6	7
Value	4	6	7	9
Pointer	right

Index	0	1	2	3	4	5	6	7
Value	1	2	3	4
Pointer					k

---

Index	0	1	2	3
Value	1	2	3	5
Pointer				left

Index	4	5	6	7
Value	4	6	7	9
Pointer		right

Index	0	1	2	3	4	5	6	7
Value	1	2	3	4	5
Pointer						k

---

여기서 left 범위가 벗어났으므로, 남은 right 들을 sorted에 추가합니다.

Index	0	1	2	3	4	5	6	7
Value	1	2	3	4	5	6	7	9
Pointer

Python 코드

def merge(arr, start, end):
    mid = (start + end) // 2
    left = start
    right = mid + 1
    sorted = [0 for _ in range(end - start + 1)]
    k = 0
    while left <= mid and right <= end:
        if arr[left] <= arr[right]:
            sorted[k] = arr[left]
            left += 1
        else:
            sorted[k] = arr[right]
            right += 1
        k += 1
    for i in range(left, mid + 1):
        sorted[k] = arr[i]
        k += 1
    for i in range(right, end + 1):
        sorted[k] = arr[i]
        k += 1

    for i in range(start, end + 1):
        arr[i] = sorted[i - start]

def merge_sort(start, end):
    if start < end:
        mid = (start + end) // 2
        merge_sort(start, mid)
        merge_sort(mid + 1, end)
        merge(start, end)

merge_sort(0, len(arr_m) - 1)
print(arr_m)

세그먼트 트리를 통한 구현

segment_tree = [0] * 2000000

def merge(left, right):
    sorted = [0] * (len(left)+len(right))
    mid = (len(left) + len(right))//2
    i = 0
    j = 0
    k = 0

    while i < len(left) and j < len(right):
        if left[i] <= right[j]:
            sorted[k] = left[i]
            i += 1
        else:
            sorted[k] = right[j]
            j += 1
        k += 1

    for l in range(j, len(right)):
        sorted[k] = right[l]
        k += 1
    for l in range(i, len(left)):
        sorted[k] = left[l]
        k += 1
    return sorted

def build(arr, node, start, end):
    if start == end:
        segment_tree[node] = [arr[start]]
        return segment_tree[node]
    mid = (start + end) // 2
    segment_tree[node] = merge(build(arr, node * 2, start, mid), build(arr, node * 2 + 1, mid + 1, end))
    return segment_tree[node]