[알고리즘] 병합 정렬(Merge Sort) 이해 with Python

 

이번 포스팅은 정렬 알고리즘 중 하나인 병합 정렬(Merge Sort)에 대한 내용을 정리하였습니다.

병합 정렬의 이해와 코드 예시, 퀵 정렬과의 차이점을 하나씩 알아보고 이해하였습니다.

---

| 병합 정렬(Merge Sort) 이해

- 병합 정렬은 배열을 분할하고 분할된 부분 배열을 정렬한 다음 병합하여

배열을 정렬하는 재귀 정렬 알고리즘 중 하나입니다.

- 언뜻 보면 퀵 정렬과 비슷해 보이지만 차이점이 있으므로 병합 정렬의 구동 방식부터 알아보겠습니다.

 

| 병합 정렬의 구동 방식 

1. 분할(Divide) : 주어진 배열을 반으로 나눔

2. 반복 : 배열의 크기가 1 이하가 될 때까지 분할 반복

3. 정복(Conquer) : 반으로 나뉜 배열을 정렬 

4. 병합(Merge) : 정렬된 배열들을 병합하여 최종적으로 정렬된 배열 생성, 

이때 정렬된 상태를 유지하면서 병합합니다.

 

코드 예시를 통해 구동 방식을 자세히 알아보겠습니다.

def merge_sort(arr):
    # 기본 단계: 배열의 길이가 1 이하이면 이미 정렬된 상태
    if len(arr) <= 1:
        return arr

    # 배열을 반으로 나누기
    mid = len(arr) // 2
    left_half = arr[:mid]
    right_half = arr[mid:]

    # 왼쪽 부분 배열을 재귀적으로 정렬
    left_half = merge_sort(left_half)
    # 오른쪽 부분 배열을 재귀적으로 정렬
    right_half = merge_sort(right_half)

    # 정렬된 부분 배열을 병합
    sorted_arr = []
    left_idx, right_idx = 0, 0

    while left_idx < len(left_half) and right_idx < len(right_half):
        # 두 부분 배열을 비교하여 더 작은 값을 결과 배열에 추가
        if left_half[left_idx] <= right_half[right_idx]:
            sorted_arr.append(left_half[left_idx])
            left_idx += 1
        else:
            sorted_arr.append(right_half[right_idx])
            right_idx += 1

    # 남은 원소들을 결과 배열에 추가
    sorted_arr.extend(left_half[left_idx:])
    sorted_arr.extend(right_half[right_idx:])

    # 최종 정렬된 배열 반환
    return sorted_arr

# 병합 정렬을 테스트하기 위한 예제
unsorted_list = [38, 27, 43, 3, 9, 82, 10]
sorted_list = merge_sort(unsorted_list)
print(sorted_list)  # [3, 9, 10, 27, 38, 43, 82]

- 코드를 보시면 배열의 길이가 1 이하 이도록 반으로 나누고 

왼쪽, 오른쪽 부분의 배열을 각각 정렬하고 병합하는 과정을 보여줍니다.

---

| 병합 정렬(Merge Sort) 장점

1. 안정한 정렬 알고리즘 

- 앞서 구동 방식에 대해 얘기할 때 정렬된 상태를 유지하면서 병합한다고 설명하였습니다.

정렬된 상태를 유지하면서 병합하는 게 무슨 뜻일까요? 

이는 같은 값의 원소들의 상대적인 순서를 유지한다는 뜻이며 

같은 값의 원소들이 다른 속성을 가질 때 중요하게 됩니다.

 

코드 예시를 통해 알아보겠습니다.

# 정렬할 학생 목록(이름, 나이)
students = [("Alice", 23), ("Bob", 22), ("Alice", 21), ("David", 22), ("Eva", 24)]

# 이름을 기준으로 안정적인 병합 정렬을 사용하여 정렬
def stable_merge_sort(arr):
    # 기본 단계: 배열의 길이가 1 이하이면 이미 정렬된 상태
    if len(arr) <= 1:
        return arr

    # 배열을 중간 지점에서 둘로 나누기
    mid = len(arr) // 2
    left_half = arr[:mid]
    right_half = arr[mid:]

    # 왼쪽과 오른쪽 부분 배열을 재귀적으로 정렬
    left_half = stable_merge_sort(left_half)
    right_half = stable_merge_sort(right_half)

    # 정렬된 부분 배열을 병합
    sorted_arr = []
    left_idx, right_idx = 0, 0

    while left_idx < len(left_half) and right_idx < len(right_half):
        # 이름을 기준으로 두 학생을 비교하여 정렬
        if left_half[left_idx][0] <= right_half[right_idx][0]:
            sorted_arr.append(left_half[left_idx])
            left_idx += 1
        else:
            sorted_arr.append(right_half[right_idx])
            right_idx += 1

    # 남은 원소들을 결과 배열에 추가
    sorted_arr.extend(left_half[left_idx:])
    sorted_arr.extend(right_half[right_idx:])

    return sorted_arr

# 이름을 기준으로 학생 목록을 정렬
sorted_students = stable_merge_sort(students)

# 정렬 결과 출력
for student in sorted_students:
    print(student)

- 구동 방식은 앞의 숫자의 리스트를 정렬하는 코드와 똑같습니다.

주요점은 위 코드에서 이름을 기준으로 학생 목록을 정렬하고 있는데

동일한 이름을 가진 학생들의 상대적인 순서가 유지됩니다.

이를 통해 병렬 정합에서 안정적으로 정렬하는 방법을 확인할 수 있습니다. 

 

2. 항상 O(n log n)의 시간 복잡도를 가짐 

- 병합 정렬은 항상 O(n log n)의 시간 복잡도를 가지는데 

이는 알고리즘의 구동 방식 때문입니다.

입력 데이터의 크기와 순서에 상관없이 배열을 반으로 나누고 

정렬하며 다시 병합하기 때문에 데이터의 순서와 크기에 영향을 받지 않습니다. 

 

따라서 데이터의 순서의 크기와 무관하게 항상 O(n log n)의 시간 복잡도를 가집니다.

---

| 퀵 정렬 (Quick Sort)와의 차이점 

1. 동작 방식:
   - 병합 정렬: 병합 정렬은 배열을 분할하고 각 부분 배열을 재귀적으로 정렬한 다음 정렬된 부분 배열을 병합하여 최종 정렬된 배열을 생성합니다. 이것은 분할 정복(divide and conquer) 방식을 따릅니다.
   - 퀵 정렬: 퀵 정렬은 배열을 피벗(pivot)을 기준으로 두 개의 부분 배열로 분할하며, 각 부분 배열을 독립적으로 정렬합니다. 분할 과정을 반복하면서 정렬을 수행합니다.
2. 안정성:
   - 병합 정렬: 안정한 정렬 알고리즘으로 같은 값의 원소의 상대적 순서가 유지됩니다.
   - 퀵 정렬: 일반적으로 안정하지 않습니다. 같은 값의 원소가 상대적인 순서를 바꿀 수 있습니다.
3. 시간 복잡도:
   - 병합 정렬: 항상 O(n log n)의 시간 복잡도를 가집니다. 이는 배열을 반으로 나누는 데 O(log n)의 시간이 들고, 각 분할된 배열을 병합하는 데 O(n)의 시간이 들기 때문입니다.
   - 퀵 정렬: 평균적으로 O(n log n)의 시간 복잡도를 가지지만, 최악의 경우 O(n^2)의 시간 복잡도를 가질 수 있습니다. 최악의 경우는 피벗 선택에 따라 다릅니다.
4. 추가 메모리 사용:
   - 병합 정렬: 추가 메모리가 필요, 이는 배열을 복사하여 사용합니다. 이로 인해 메모리 사용량이 더 많을 수 있습니다.
   - 퀵 정렬: 일반적으로 추가 메모리를 거의 사용하지 않으므로 메모리 효율적입니다.
5. 최악의 경우:
   - 병합 정렬: 최악의 경우에도 항상 일정한 성능을 보여줍니다. 따라서 안정한 성능이 중요한 경우에 사용됩니다.
   - 퀵 정렬: 최악의 경우에 성능이 나빠질 수 있지만, 무작위로 선택된 피벗에 따라 최악의 경우 발생 확률을 줄이기 위한 최적화가 가능합니다.

---

| 마무리 

- 병합 정렬에 대해 정리해 보았습니다.

퀵 정렬과 비슷해 보이는 구동 방식을 보이지만 실제로 차이가 있었고

때에 따라 퀵 정렬과, 병합 정렬 중 선택하여 알고리즘을 사용하는 것이 좋을 것이라 배웠습니다.

 

틀린 점이나 질문이 있으시면 댓글로 남겨주세요!

 

다음 포스팅으로 찾아오겠습니다.

 

감사합니다 :)