[파이썬] 병합 정렬 (Merge Sort)의 구현과 특징

01 Sep 2023

python

병합 정렬은 정렬 알고리즘 중에서 가장 효율적인 알고리즘 중 하나입니다. 이 알고리즘은 주어진 배열을 반으로 나눈 후, 각각의 반을 재귀적으로 정렬한 뒤, 정렬된 두 개의 반을 병합하여 최종적으로 정렬된 배열을 얻는 방식으로 동작합니다.

구현

병합 정렬을 Python으로 구현하는 방법을 알아보겠습니다.

def merge_sort(arr):
    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)
    
    return merge(left_half, right_half)
    
def merge(left, right):
    merged = []
    left_idx, right_idx = 0, 0
    
    while left_idx < len(left) and right_idx < len(right):
        if left[left_idx] < right[right_idx]:
            merged.append(left[left_idx])
            left_idx += 1
        else:
            merged.append(right[right_idx])
            right_idx += 1
    
    while left_idx < len(left):
        merged.append(left[left_idx])
        left_idx += 1
    
    while right_idx < len(right):
        merged.append(right[right_idx])
        right_idx += 1
        
    return merged

위의 코드에서 merge_sort 함수는 주어진 배열을 반으로 나눈 뒤, 각각의 반을 재귀적으로 merge_sort 함수를 호출하여 정렬한 뒤, merge 함수를 통해 두 개의 정렬된 배열을 병합하여 최종적으로 정렬된 배열을 반환합니다.

merge 함수는 두 개의 정렬된 배열을 받아서 하나의 정렬된 배열로 병합하는 역할을 합니다. 두 개의 정렬된 배열의 원소들을 차례대로 비교하면서 작은 값을 결과 배열에 추가합니다.

특징

병합 정렬은 다음과 같은 특징을 가지고 있습니다:

안정적인 정렬 알고리즘: 원본 배열에서 동일한 값을 가진 원소의 상대적인 순서가 정렬 후에도 유지됩니다.
분할 정복(Divide and Conquer) 알고리즘: 문제를 작은 부분으로 분해하고, 각각을 해결한 후, 결과를 결합하여 원래 문제를 해결하는 방식으로 동작합니다.
시간 복잡도: 병합 정렬의 시간 복잡도는 O(n log n)으로, 평균적으로 매우 효율적인 알고리즘입니다.
공간 복잡도: 추가적인 배열을 사용하므로 O(n)의 공간 복잡도가 필요합니다.

병합 정렬은 대부분의 상황에서 효율적인 알고리즘으로 사용될 수 있으며, 이미 정렬되어 있는 배열의 정렬이나 대량의 데이터를 정렬하는데 유용합니다. 그러나 정렬을 위한 추가적인 배열을 필요로 하기 때문에 메모리 사용량이 크다는 단점이 있습니다.