합병 정렬

합병 정렬(merge sort) 알고리즘

- 하나의 리스트를 두 개의 균등한 크기로 분할하고 분할된 부분 리스트를 정렬한 다음, 두 개의 정렬된 부분 리스트를 합하여 전체가 정렬된 리스트가 되게 하는 방법이다.
- 합병 정렬은 다음의 단계들로 이루어진다.
    - 분할(Divide): 입력 배열을 같은 크기의 2개의 부분 배열로 분할한다.
    - 정복(Conquer): 부분 배열을 정렬한다. 부분 배열의 크기가 충분히 작지 않으면 순환 호출 을 이용하여 다시 분할 정복 방법을 적용한다.
    - 결합(Combine): 정렬된 부분 배열들을 하나의 배열에 합병한다.
- 합병 정렬의 과정
   - 추가적인 리스트가 필요하다.
   - 각 부분 배열을 정렬할 때도 합병 정렬을 순환적으로 호출하여 적용한다.
   - 합병 정렬에서 실제로 정렬이 이루어지는 시점은 2개의 리스트를 합병(merge)하는 단계이다.

 

합병 정렬(merge sort) 알고리즘의 예제

- 배열에 27, 10, 12, 20, 25, 13, 15, 22이 저장되어 있다고 가정하고 자료를 오름차순으로 정렬해 보자.
- 2개의 정렬된 리스트를 합병(merge)하는 과정
   1. 2개의 리스트의 값들을 처음부터 하나씩 비교하여 두 개의 리스트의 값 중에서 더 작은 값을 새로운 리스트(sorted)로 옮긴다.
   2. 둘 중에서 하나가 끝날 때까지 이 과정을 되풀이한다.
   3. 만약 둘 중에서 하나의 리스트가 먼저 끝나게 되면 나머지 리스트의 값들을 전부 새로운 리스트(sorted)로 복사한다.
   4. 새로운 리스트(sorted)를 원래의 리스트(list)로 옮긴다.

 

합병 정렬(merge sort) 알고리즘의 특징

- 단점
   - 만약 레코드를 배열(Array)로 구성하면, 임시 배열이 필요하다.
   - 제자리 정렬(in-place sorting)이 아니다.
   - 레코드들의 크기가 큰 경우에는 이동 횟수가 많으므로 매우 큰 시간적 낭비를 초래한다.

- 장점
   - 안정적인 정렬 방법
   - 데이터의 분포에 영향을 덜 받는다. 즉, 입력 데이터가 무엇이든 간에 정렬되는 시간은 동일하다. (O(nlog₂n)로 동일)
   - 만약 레코드를 연결 리스트(Linked List)로 구성하면, 링크 인덱스만 변경되므로 데이터의 이동은 무시할 수 있을 정도로 작아진다.
        - 제자리 정렬(in-place sorting)로 구현할 수 있다.
   - 따라서 크기가 큰 레코드를 정렬할 경우에 연결 리스트를 사용한다면, 합병 정렬은 퀵 정렬을 포함한 다른 어떤 졍렬 방법보다 효율적이다.

 

합병 정렬의 시간 복잡도

T(n) = nlog₂n(비교) + 2nlog₂n(이동) = 3nlog₂n = O(nlog₂n)

 

정렬 알고리즘 시간복잡도 비교

- 단순(구현 간단)하지만 비효율적인 방법
     - 삽입 정렬, 선택 정렬, 버블 정렬
- 복잡하지만 효율적인 방법
     - 퀵 정렬, 힙 정렬, 합병 정렬, 기수 정렬

 

출처 : https://gmlwjd9405.github.io/2018/05/08/algorithm-merge-sort.html