합병 정렬(Merge Sort) 알고리즘 파이썬 예제와 설명

합병 정렬(Merge Sort)은 분할 정복(Divide and Conquer) 알고리즘의 하나입니다. 분할 정복 알고리즘은 큰 문제를 작은 문제로 분할하고, 각각의 작은 문제를 해결한 후에 그 결과를 이용하여 큰 문제를 해결하는 방식입니다.

합병 정렬의 구체적인 과정은 다음과 같습니다.

1. 배열을 두 개의 부분 배열로 분할합니다. 이때 분할되는 부분 배열의 크기는 대략 절반으로 나누어집니다.
2. 각각의 부분 배열을 재귀적으로 합병 정렬을 수행합니다.
3. 정렬된 두 개의 부분 배열을 합병합니다. 이때, 두 부분 배열의 첫 번째 원소부터 비교하여 작은 순서대로 새로운 배열에 저장합니다.
4. 분할된 부분 배열의 크기가 1이 될 때까지 위의 과정을 반복합니다.

아래는 합병 정렬의 구현 예시입니다. 배열을 합병 정렬하는 함수 `merge_sort()`는 재귀적으로 구현되어 있습니다.

def merge_sort(arr):
    if len(arr) <= 1:
        return arr
    
    mid = len(arr) // 2
    left_arr = arr[:mid]
    right_arr = arr[mid:]
    
    left_arr = merge_sort(left_arr)
    right_arr = merge_sort(right_arr)
    
    return merge(left_arr, right_arr)
    
def merge(left_arr, right_arr):
    merged = []
    left_index, right_index = 0, 0
    
    while left_index < len(left_arr) and right_index < len(right_arr):
        if left_arr[left_index] < right_arr[right_index]:
            merged.append(left_arr[left_index])
            left_index += 1
        else:
            merged.append(right_arr[right_index])
            right_index += 1
    
    merged += left_arr[left_index:]
    merged += right_arr[right_index:]
    
    return merged

합병 정렬은 평균 시간 복잡도가 O(n log n)으로 상대적으로 빠른 정렬 알고리즘 중 하나입니다. 하지만 메모리 사용량이 크다는 단점이 있습니다. 두 개의 부분 배열을 복사하여 만들어야 하기 때문입니다.