정렬 | 병합정렬 | 안정적이고 강력한 정렬 알고리즘

병합 정렬(Merge Sort) 알고리즘 자세히 살펴보기

정렬 알고리즘 중 하나인 병합 정렬(Merge Sort)은 분할 정복(Divide and Conquer) 전략을 사용하여 데이터를 정렬하는 방법입니다. 이 글에서는 병합 정렬의 개념과 동작 방식, 그리고 Python을 활용한 구현 방법까지 자세히 살펴보겠습니다.

---

1. 병합 정렬의 개념

병합 정렬은 다음과 같은 순서로 데이터를 정렬합니다:

1. 분할(Divide): 리스트를 절반으로 나누어 더 이상 나눌 수 없을 때까지 분할합니다.
2. 정복(Conquer): 각각의 리스트를 재귀적으로 정렬합니다.
3. 병합(Merge): 정렬된 리스트를 하나로 합쳐 정렬된 형태로 만듭니다.

병합 정렬은 안정 정렬(Stable Sort)이며, 최악, 최선, 평균 시간 복잡도가 모두 이므로 큰 데이터셋을 정렬하는 데 매우 유용한 알고리즘입니다.

---

2. 병합 정렬의 동작 방식

예를 들어, 리스트 [1,5,2,6,7,2,4,8,9,4,5,3,1]을 병합 정렬하는 과정을 단계별로 살펴보겠습니다.

1. 리스트를 두 개로 나눕니다:
2. [1,5,2,6,7,2] | [4,8,9,4,5,3,1]
3. 각각의 리스트를 다시 두 개로 나눕니다.
4. [1,5,2] | [6,7,2] | [4,8,9] | [4,5,3,1]
5. 원소가 1~2개가 될 때까지 계속 나눕니다.
6. 이제 작은 리스트부터 차례대로 병합하면서 정렬합니다.
7. 마지막에는 정렬된 두 개의 리스트를 합쳐 최종 정렬된 결과를 얻습니다.

---

3. 병합 정렬의 구현 (Python 코드)

이제 병합 정렬을 Python 코드로 구현해 보겠습니다.

3.1. 두 개의 정렬된 리스트를 병합하는 함수

def merge(left: list, right: list) -> list:
    """두 개의 정렬된 리스트를 병합하는 함수"""
    result = [None] * (len(left) + len(right))  # 결과 리스트 생성
    i, j = 0, 0  # 각 리스트의 인덱스 초기화
    
    for k in range(len(result)):
        if i < len(left) and j < len(right):  # 두 리스트 모두 요소가 남아 있을 경우
            if left[i] <= right[j]:
                result[k] = left[i]
                i += 1
            else:
                result[k] = right[j]
                j += 1
        elif i >= len(left):  # 왼쪽 리스트의 모든 요소를 사용한 경우
            result[k] = right[j]
            j += 1
        elif j >= len(right):  # 오른쪽 리스트의 모든 요소를 사용한 경우
            result[k] = left[i]
            i += 1
    
    return result

이 함수는 두 개의 정렬된 리스트를 받아 하나의 정렬된 리스트로 합칩니다.

3.2. 병합 정렬 함수

def merge_sort(seq: list) -> None:
    """병합 정렬 알고리즘 구현"""
    if len(seq) <= 1:
        return  # 리스트가 1개 이하이면 정렬할 필요 없음
    
    mid = len(seq) // 2  # 리스트를 반으로 나눔
    left = seq[:mid]  # 왼쪽 부분 리스트
    right = seq[mid:]  # 오른쪽 부분 리스트
    
    merge_sort(left)  # 왼쪽 리스트 재귀 정렬
    merge_sort(right)  # 오른쪽 리스트 재귀 정렬
    
    merged = merge(left, right)  # 정렬된 두 리스트 병합
    for k in range(len(seq)):
        seq[k] = merged[k]  # 정렬된 리스트를 원래 리스트에 복사

이제 정렬할 리스트를 넣고 실행해보겠습니다.

3.3. 병합 정렬 실행 예제

arr = [1, 5, 2, 6, 7, 2, 4, 8, 9, 4, 5, 3, 1]
merge_sort(arr)
print(arr)

출력 결과

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

---

4. 병합 정렬의 시간 복잡도 분석

병합 정렬의 시간 복잡도는 모든 경우에 대해 입니다.

• 분할 단계: 리스트를 계속 반으로 나누므로 총 log n 단계가 필요합니다.
• 병합 단계: 각 단계에서 모든 원소를 한 번씩 비교 및 정렬하므로 O(n) 시간이 필요합니다.
• 전체 복잡도:

장점과 단점

장점:

• 안정 정렬로, 같은 값이 있더라도 기존 순서를 유지합니다.
• 최악, 평균, 최선의 경우 모두 O(n log n)으로 일관된 성능을 가집니다.
• 데이터 크기가 클 경우에도 효과적인 정렬 방식입니다.

단점:

• 추가적인 메모리 공간이 필요하므로 메모리 사용량이 많습니다.
• 작은 크기의 리스트에서는 삽입 정렬보다 비효율적일 수 있습니다.

---

5. 결론

병합 정렬은 정렬 알고리즘 중에서 일관된 성능과 안정성을 갖춘 강력한 방법입니다. 특히 대량의 데이터를 다룰 때 효과적이므로 대규모 데이터 정렬, 파일 정렬, 외부 정렬 등에 자주 사용됩니다.

 

 

이번 게시글에서는 재귀를 사용하여 병합 정렬을 구현하였습니다.

이 재귀적 원리를 더욱더 자세하게 다음 게시글에서 원리를 설명하도록 하겠습니다.