머지 소트 편집하기

'''머지 소트'''(Merge Sort)는 분할 정복(divide and conquer) 방식의 정렬 알고리즘으로, 데이터를 반으로 나누어 정렬한 후 병합하는 방식으로 동작한다. 안정 정렬(stable sort)에 속하며, 평균 및 최악의 경우 시간 복잡도가 O(n log n)으로 일정하다. (Θ(n log n)
==개요==
머지 소트는 문제를 작은 부분으로 나누고, 이를 정렬한 후 병합하는 방식으로 동작한다.  알고리즘의 동작 과정은 다음과 같다.
#리스트를 반으로 나눈다.
#각각의 부분 리스트를 재귀적으로 정렬한다.
#정렬된 두 리스트를 병합하여 하나의 정렬된 리스트를 만든다.
이 알고리즘은 재귀적으로 구현될 수도 있고, 반복문을 사용한 비재귀적(반복문) 방식으로도 구현될 수 있다.
==알고리즘 과정==
머지 소트의 동작 과정은 다음과 같다.
===1. 분할 (Divide)===
*주어진 리스트를 두 개의 하위 리스트로 분할한다.
*리스트의 크기가 1이 될 때까지 재귀적으로 나눈다.
예제:  정렬할 배열이 다음과 같다고 가정한다.<syntaxhighlight lang="text">
[38, 27, 43, 3, 9, 82, 10]
</syntaxhighlight>이 배열을 반으로 나누면 다음과 같이 된다.<syntaxhighlight lang="text">
[38, 27, 43, 3]    [9, 82, 10]
</syntaxhighlight>이 과정을 계속 반복하면, 모든 부분 배열의 크기가 1이 될 때까지 나눠진다.<syntaxhighlight lang="text">
[38] [27] [43] [3] [9] [82] [10]
</syntaxhighlight>
===2. 정복 (Conquer)===
*각각의 하위 리스트를 개별적으로 정렬한다.
정렬된 두 개의 리스트를 병합하며 정렬을 수행한다.

1단계 병합 후:<syntaxhighlight lang="text">
[27, 38] [3, 43] [9, 10] [82]
</syntaxhighlight>2단계 병합 후:<syntaxhighlight lang="text">
[3, 27, 38, 43] [9, 10, 82]
</syntaxhighlight>
===3. 병합 (Merge)===
*두 개의 정렬된 리스트를 하나의 정렬된 리스트로 합친다.
최종 병합 과정 후:<syntaxhighlight lang="text">
[3, 9, 10, 27, 38, 43, 82]
</syntaxhighlight>이제 전체 리스트가 정렬되었다.
==시간 복잡도==
머지 소트의 시간 복잡도는 다음과 같이 분석할 수 있다.
*'''최선의 경우(Best Case)''' : Ω(n log n)
*'''평균적인 경우(Average Case)''' : Θ(n log n)
*'''최악의 경우(Worst Case)''' : O(n log n)
머지 소트는 항상 O(n log n)의 시간 복잡도를 보장하며, 입력이 어떠한 순서로 되어 있더라도 성능이 일정하다.
==공간 복잡도==
머지 소트는 추가적인 메모리 공간이 필요하며, 재귀 호출과 병합 과정에서 O(n)의 추가 공간을 사용한다.
==구현==
다음은 파이썬(Python)으로 구현된 머지 소트 예제이다.<syntaxhighlight lang="python">
def merge_sort(arr):
    if len(arr) <= 1:
        return arr

    mid = len(arr) // 2
    left_half = merge_sort(arr[:mid])
    right_half = merge_sort(arr[mid:])

    return merge(left_half, right_half)

def merge(left, right):
    sorted_arr = []
    i = j = 0

    while i < len(left) and j < len(right):
        if left[i] < right[j]:
            sorted_arr.append(left[i])
            i += 1
        else:
            sorted_arr.append(right[j])
            j += 1

    sorted_arr.extend(left[i:])
    sorted_arr.extend(right[j:])
    return sorted_arr

# 사용 예제
arr = [38, 27, 43, 3, 9, 82, 10]
sorted_arr = merge_sort(arr)
print(sorted_arr)  # 출력: [3, 9, 10, 27, 38, 43, 82]

</syntaxhighlight>
==머지 소트의 특징==
*'''안정 정렬(Stable Sort)''' : 동일한 값의 원소들이 정렬 후에도 상대적인 순서를 유지한다.
*'''일관된 성능''' : 최선, 평균, 최악의 경우 시간 복잡도가 O(n log n)으로 일정하다.
*'''추가적인 메모리 사용''' : 병합 과정에서 추가적인 메모리 공간이 필요하여 O(n)의 공간 복잡도를 가진다.
*'''큰 데이터 정렬에 유리''' : 퀵 정렬과 달리 최악의 경우에도 O(n log n)을 유지하여 안정적인 성능을 제공한다.
==응용==
머지 소트는 다음과 같은 상황에서 유용하게 사용된다.
*연결 리스트(Linked List) 정렬 - 연결 리스트에서는 추가적인 메모리 사용이 상대적으로 적어 퀵 정렬보다 유리할 수 있음.
*외부 정렬(External Sorting) - 데이터가 메모리에 한 번에 적재되지 않을 때 사용됨.
==같이 보기==
*[[퀵 정렬]]
*[[힙 정렬]]
*[[삽입 정렬]]
*[[시간 복잡도]]
*[[정렬 알고리즘]]
==참고 문헌==
*Cormen, T. H., Leiserson, C. E., Rivest, R. L., & Stein, C. (2009). ''Introduction to Algorithms''. MIT Press.
*Knuth, D. E. (1997). ''The Art of Computer Programming''. Addison-Wesley.
[[분류:알고리즘]]