병합 정렬 (Merge Sort) 알고리즘 (with Python3)

1. 병합 정렬

병합 정렬(Merge sort)은 그룹을 반으로 나눈다음 합칠때 크기에 맞게 합친다. 이 과정을 재귀적으로 수행한다. (그림 참고)

 

Credit. https://en.wikipedia.org/wiki/Merge_sort

 

2. 코딩

아래 코드는 unittest 기반으로 작성되었다.

2.1. 일반적인 병합 정렬

      

      

      

    
    

      <python />
    
# -*- coding: utf-8 -*-

import unittest


class Exam10(unittest.TestCase):

    @classmethod
    def setUp(cls):
        pass

    def test_merge_sort(self):
        """일반적인 병합 정렬"""
        def _merge_sort(group):
            # 재귀 종료 조건: 그룹이 없을때
            n = len(group)
            if n <= 1:
                return

            # 반으로 그룹을 나눈다.
            mid_idx = n // 2
            group1 = group[:mid_idx]
            group2 = group[mid_idx:]
            # print(group, group1, group2)

            # 재귀적으로 병합 정렬을 수행한다.
            _merge_sort(group1)
            _merge_sort(group2)

            # 정렬한다.
            idx, idx1, idx2 = 0, 0, 0  # 전체 그룹 인덱스, 그룹1 인덱, 그룹2 인덱스
            while idx1 < len(group1) and idx2 < len(group2):
                if group1[idx1] < group2[idx2]:
                    group[idx] = group1[idx1]
                    idx1 += 1
                else:
                    group[idx] = group2[idx2]
                    idx2 += 1
                idx += 1

            # 그룹에 남아있는 원소를 넣는다.
            while idx1 < len(group1):
                group[idx] = group1[idx1]
                idx1 += 1
                idx += 1
            while idx2 < len(group2):
                group[idx] = group2[idx2]
                idx2 += 1
                idx += 1

        data = [38, 27, 43, 3, 9, 82, 10]
        _merge_sort(data)

        self.assertEqual([3, 9, 10, 27, 38, 43, 82], data)


if __name__ == "__main__":
    unittest.main()

2.2. 파이썬을 이용한 병합 정렬

크게 차이점은 없다. _merge_sort() 가 return 값이 있는지 없는지에 대한 차이점이 있다.

      

      

      

    
    

      <python />
    
# -*- coding: utf-8 -*-

import unittest


class Exam10(unittest.TestCase):

    @classmethod
    def setUp(cls):
        pass

    def test_merge_sort_with_python(self):
        """파이썬을 이용한 병합 정렬"""
        def _merge_sort(group):
            # 종료 조건 설정
            n = len(group)
            if n <= 1:
                return group

            # 그룹 나누기
            mid_idx = n // 2
            group1 = _merge_sort(group[:mid_idx])
            group2 = _merge_sort(group[mid_idx:])

            # 정렬
            result = list()
            while group1 and group2:
                result.append(group1.pop(0) if group1[0] < group2[0] else group2.pop(0))
            result.extend(group1)
            result.extend(group2)
            # print(result)
            return result

        data = [38, 27, 43, 3, 9, 82, 10]
        sorted_data = _merge_sort(data)

        self.assertEqual([3, 9, 10, 27, 38, 43, 82], sorted_data)


if __name__ == "__main__":
    unittest.main()

이렇게 반으로 나누어서 문제를 푸는 방식을 분할 정복(Divide and Conquer)이라고 한다.

 

분할 정복은 시간복잡도가 O(N * logN) 이다. 선택 정렬이나 삽입 정렬의 시간 복잡도 O(N^2) 보다 낮아, 비교적 빠르다.

즉, 개수가 많아질수록 병합정렬(Merge Sort)을 이용하는것이 효율적이다.

 

다른 방법의 정렬 알고리즘은 아래를 참고한다.

• 2020/03/21 - [Algorithm] - 선택 정렬 (Selection Sort) 알고리즘 (with Python3)
• 2020/03/21 - [Algorithm] - 삽입 정렬 (Insertion Sort) 알고리즘 (with Python3)
• 2020/03/25 - [Algorithm] - 퀵 정렬 (Quick Sort) 알고리즘 (with Python3)
• 2020/03/25 - [Algorithm] - 버블 정렬 (Bubble Sort) 알고리즘 (with Python3)

3. Reference

• https://thebook.io/006935/part03/ch10/04-01/