[python] 병합 정렬

07 Dec 2023

python

병합 정렬(Merge Sort)은 주어진 배열을 반으로 나눈 뒤, 각각을 정렬한 다음 병합하여 전체 배열을 정렬하는 알고리즘입니다. 정렬할 배열을 절반으로 나누는 방식이므로 분할 정복(Divide and Conquer) 알고리즘에 속합니다.

작동 원리

병합 정렬의 작동 과정은 다음과 같습니다:

주어진 배열을 반으로 나눕니다.
나눈 각 배열에 대해 재귀적으로 병합 정렬을 수행합니다.
정렬된 두 배열을 병합하여 하나의 정렬된 배열로 만듭니다.

다음은 병합 정렬의 예시입니다.

def merge_sort(arr):
    if len(arr) <= 1:
        return arr
    
    mid = len(arr) // 2
    left = arr[:mid]
    right = arr[mid:]
    
    left = merge_sort(left)
    right = merge_sort(right)
    
    return merge(left, right)

def merge(left, right):
    result = []
    i, j = 0, 0
    
    while i < len(left) and j < len(right):
        if left[i] <= right[j]:
            result.append(left[i])
            i += 1
        else:
            result.append(right[j])
            j += 1
    
    while i < len(left):
        result.append(left[i])
        i += 1
    
    while j < len(right):
        result.append(right[j])
        j += 1
    
    return result

arr = [5, 2, 4, 6, 1, 3]
sorted_arr = merge_sort(arr)
print(sorted_arr)  # [1, 2, 3, 4, 5, 6]

위의 코드에서 merge_sort 함수는 주어진 배열을 두 개로 나눈 뒤, 각각을 정렬하고 병합하여 정렬된 배열을 반환합니다. merge 함수는 두 개의 정렬된 배열을 받아 하나의 정렬된 배열을 생성합니다.

병합 정렬은 배열을 계속해서 반으로 나누기 때문에 시간 복잡도는 O(n log n)입니다.

결론

병합 정렬은 배열을 효율적이고 안정적으로 정렬하는 알고리즘입니다. 분할 정복을 이용하여 작동하며, 시간 복잡도도 좋은 편입니다. 따라서 대부분의 경우에 사용할 수 있습니다.

참고: 위키백과 - 병합 정렬