[정렬] Merge Sort 개념 정리 및 관련 문제 풀기

이번 포스트에서는 Merge Sort에 대한 개념에 대해 알아보기 관련 문제를 풀어보겠습니다.

 

 

개념 정리

Merge Sort는 번역하면 병합 정렬이라고 합니다. Merge Sort는 대표적인 Divide & Conquer 알고리즘입니다. 즉 분할을 해서 작은 사이즈를 먼저 해결하고 나서 합치는 것을 의미합니다. 이 전략이 좋은 이유는 처음부터 많은 양의 비교를 하지 않고 작은 단위부터 정렬된 배열들을 만들어서 합칠때 두 정렬된 배열을 비교하면 되기 때문입니다. 

 

정렬된 배열을 비교하는 것은 일반적인 정렬보다 간단합니다. 왜냐하면 각 배열이 이미 정렬되어 있기 때문에 가장 앞에 있는 것들만 비교하면 됩니다.

예를 들어서 배열 [1, 3, 5, 7] 과 [2, 4, 6, 8] 을 정렬한다고 가정하겠습니다. 두 배열은 모두 정렬된 상태입니다. 이 두 배열을 합쳐서 정렬하는 방법 중 하나는 [1, 3, 5, 7, 2, 4, 6, 8] 배열을 만들어서 정렬하는 것입니다. 만약 정렬되지 않은 두 배열을 정렬해야 한다면 이렇게 할 수 있지만, 정렬된 배열끼리는 이런 과정을 거칠 필요가 없습니다.

 

두 배열이 정렬되었다는 점을 이용하면 매 비교마다 가장 앞에 있는 값만 비교하여 남은 수 중 가장 작은 것을 찾을 수 있습니다. 왜냐면 그 수는 이미 해당 배열에서는 가장 작은 수이고, 다른 배열의 가장 작은 수보다 작으면 전체 중에 가장 작은 수가 됩니다.

 

과정을 살펴보면 아래와 같습니다.

[1, 3, 5, 7], [2, 4, 6, 8] --> 1 < 2 이므로 가장 작은 수는 1

[3, 5, 7], [2, 4, 6, 8] --> 3 > 2 이므로 가장 작은 수는 2

[3, 5, 7], [4, 6, 8] --> 3 < 4 이므로 가장 작은 수는 3

[5, 7], [4, 6, 8] ...

 

위 과정을 진행하다보면 한 쪽 배열이 먼저 끝나게 되는데, 그 때는 남은 배열을 그대로 쓰면 됩니다.

이 알고리즘의 속도는 O(N + M)입니다. (N: 첫번째 배열 길이, M: 두번째 배열 길이)

순회하는 동안 하나의 원소는 반드시 제거되기 때문에 최대 N+M 번의 반복 작업이 발생합니다. 다만, 이 작업을 진행하기 위해서는 별도의 배열을 추가로 사용해야 합니다. 따라서 공간 복잡도는 다른 정렬 알고리즘에 비해 높은 편입니다.

 

위와 같이 두 정렬된 배열을 합치는 알고리즘을 사용하여 Merge Sort를 구현하면 다음과 같습니다.

 

1. 전체 배열을 이등분 합니다.

2. 분할된 배열에서 MergeSort를 진행합니다.

3. 두 배열이 모두 정렬되면, 하나의 리스트로 합칩니다.

 

예시를 통해서 살펴보겠습니다.

출처:&nbsp;https://www.geeksforgeeks.org/merge-sort/

 

보시면 최종적으로는 원소가 1개가 남을때까지 분리합니다. 다만 1개가 남는다는 건 이미 정렬이 되어 있다는 뜻이기 때문에 더 이상 나눌 필요가 없습니다.

 

복잡도

시간 복잡도: O(NlogN)

시간 복잡도는 Operation 수를 따져보면 되는데, 두 배열을 Merge하는 곳에서 Operation이 발생합니다. 즉, 두 배열을 합칠때 O(N) 만큼의 시간이 소요됩니다. 하지만 여기서 한 가지 더 봐야할 것은 바로 Recursion(재귀)방식을 쓴다는 것입니다. 재귀 함수의 깊이는 N -> 1이 될때까지 나누기 때문에 logN이 됩니다. 따라서 O(NlogN) 의 시간 복잡도를 갖습니다.

 

공간 복잡도: O(N)

공간 복잡도는 정확히 O(N)은 아니지만, 연산 당시 순간 필요한 메모리 공간이 배열의 길이만큼만 있으면 되기 때문에 O(N)이 됩니다. 해당 배열은 함수를 빠져나오면서 사라지므로 다른 함수에서는 사용되지 않습니다.

 

관련 문제 

삽입 정렬에서 풀지 못했던 문제를 Merge Sort를 활용하여 풀어보겠습니다.

Sort an Array - LeetCode

class Solution:
    def mergeTwoArray(self, nums, left, mid, right):
        # i는 왼쪽배열의 첫번째 원소, j는 오른쪽 배열의 첫번째 원소입니다.
        i, j = left, mid+1
        
        # 임의의 배열을 할당하여 정렬된 배열을 기록합니다.
        temp = []
        
        # 한 쪽 배열에 원소가 없는 상황이 나올때까지 반복합니다.
        # 한 번 반복할 때마다 temp에 가장 작은 수가 들어갑니다.
        while i <= mid and j <= right:
            if nums[i] < nums[j]:
                temp.append(nums[i])
                i+=1
            else:
                temp.append(nums[j])
                j+=1
                
        # 만약 왼쪽 배열이 아직 남아있으면 temp에 순서대로 넣어줍니다.
        while i<=mid:
            temp.append(nums[i])
            i+=1
        
        # 만약 오른쪽 배열이 아직 남아있으면 temp에 순서대로 넣어줍니다.
        while j <= right:
            temp.append(nums[j])
            j+=1
        
        # temp에 정렬된 배열을 nums에 업데이트 합니다.
        for i in range(len(temp)):
            nums[left + i] = temp[i]
            
    # mergeSort는 배열중에서 [left ~ right] 인덱스에 포함되는 배열만 정렬합니다.
    def mergeSort(self, nums, left, right):
        # 만약 개수가 1개라면 이미 정렬되어 있으므로 바로 리턴합니다.
        if right - left == 0:
            return
        
        # 배열을 두개로 나누기 위해 중간값을 구합니다.
        mid = (left + right) // 2
        
        # 왼쪽 배열을 정렬합니다.
        self.mergeSort(nums, left, mid)
        
        # 오른쪽 배열을 정렬합니다.
        self.mergeSort(nums, mid+1, right)
        
        # 정렬된 두 배열을 합칩니다.
        self.mergeTwoArray(nums, left, mid, right)
        
        
    def sortArray(self, nums: List[int]) -> List[int]:
        # 처음부터 끝까지 정렬을 진행합니다.
        self.mergeSort(nums, 0, len(nums)-1)
        
        return nums

 

위와 같이 Merge Sort를 사용하면 제한시간 내에 결과가 나오기 때문에 Accept를 받으실 수 있습니다.

 

이번에는 조금 더 어려운 문제를 풀어보겠습니다.

Merge k Sorted Lists - LeetCode

 

위 문제는 LinkedNode로 구성된 여러 노드들을 정렬하는 문제입니다. LinkedList는 이미 정렬이 되어 있는 상태이므로 위와 같이 나눠서 정렬하면 됩니다. 다만 지금은 이미 나눠진 상태에서 합치는 것이기 때문에 굳이 나누는 작업을 할 필요는 없고, 둘 씩 합치면 됩니다.

# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, val=0, next=None):
#         self.val = val
#         self.next = next

from queue import PriorityQueue
class Solution:
    def mergeKLists(self, lists: List[Optional[ListNode]]) -> Optional[ListNode]:
        
        # 리스트가 비어 있으면 None을 리턴합니다.
        if len(lists) == 0:
            return None
        
        # 리스트가 1개가 남을 때까지 반복합니다.
        while len(lists) > 1:
            
            # 새로운 리스트를 만들어서 Merge된 결과를 넣습니다.
            new_list = []
            for i in range(0, len(lists), 2):
                # 만약 다음 배열이 없으면 그대로 다음단계로 넘어갑니다.
                if i + 1 == len(lists):
                    new_list.append(lists[i])
                # 있으면 mergeTwo함수를 통해 병합된 노드를 새로운 리스트에 추가합니다.
                else:
                    new_list.append(self.mergeTwo(lists[i], lists[i + 1]))
            # 현재 리스트를 새로운 리스트로 반환합니다.
            lists = new_list
        
        return lists[0]
    
    def mergeTwo(self, l1, l2):
        # curr은 계속 움직이기 때문에 head라는 변수를 두어 첫번째 노드를 표시합니다.
        head = curr = ListNode()
        # 두 노드 모두 존재할 때만 반복합니다.
        while l1 and l2:
            if l1.val <= l2.val:
                curr.next = l1
                l1 = l1.next
            else:
                curr.next = l2
                l2 = l2.next
            curr = curr.next
        
        # 첫 번째 노드가 남은 경우 curr에 연결합니다.
        if l1:
            curr.next = l1
            
        # 두 번째 노드가 남은 경우 curr에 연결합니다.            
        if l2:
            curr.next = l2
            
        return head.next

★ 생각해보기

위 풀이에서는 새로운 리스트에 결과를 추가하는 방법으로 공간 복잡도를 O(N)으로 구현했습니다. LinkedList라는 점을 이용하면 이것은 O(1)로 만들 수 있습니다! 

 

바로 두 배열을 합친 결과를 왼쪽 원소에 저장하는 것입니다. 

 

예를 들어서 [1,2,3,4,5,6] 번 노드가 있다고 가정하겠습니다.

첫번째 작업에서 (1, 2), (3,4), (5,6)번을 Merge하고 각 결과를 1, 3, 5 번에 넣습니다. 그러면 결과는 [1, _, 3, _, 5, _] 가 될 것입니다. 

두번째 작업에서는 (1,3), (5) 번을 Merge하고 각 결과를 1, 5번에 넣습니다. 결과는 [1, _, _, _, 5, _]가 될 것입니다.

마지막으로 (1, 5)번을 Merge하고 결과를 1번에 넣습니다. 결과는 [1, _, _, _, _, _] 이 됩니다.

 

이때 1번은 모든 리스트를 Merge한 결과물이므로 현재 lists의 첫번째 원소를 반환하면 됩니다.

 

 

---

Merge Sort를 공부하실 때 Insertion Sort(삽입 정렬)와 비교해보시면 좋을 것 같습니다 :)

[정렬] Insertion Sort(삽입 정렬) 기본 개념 및 관련 문제 풀기!