병합 정렬 (Merge Sort)

병합 정렬(Merge Sort)은 분할 정복(Divide and Conquer) 기법을 사용하는 효율적인 비교 기반 정렬 알고리즘이다. 병합 정렬은 리스트를 반으로 나누고, 각 부분 리스트를 재귀적으로 정렬한 다음, 정렬된 부분 리스트들을 병합하여 전체 리스트를 정렬한다.

동작 원리

병합 정렬은 다음과 같은 단계를 따른다:

1. 분할 (Divide): 리스트를 반으로 나누어 두 개의 부분 리스트로 분할한다.
2. 정복 (Conquer): 각 부분 리스트를 재귀적으로 병합 정렬을 사용하여 정렬한다.
3. 병합 (Combine): 정렬된 두 부분 리스트를 병합하여 하나의 정렬된 리스트로 만든다.

알고리즘 단계

1. 리스트가 비어 있거나 하나의 요소만 포함하고 있으면 이미 정렬된 것으로 간주하고 반환한다.
2. 그렇지 않으면 리스트를 두 개의 부분 리스트로 분할한다.
3. 각 부분 리스트를 병합 정렬을 사용하여 재귀적으로 정렬한다.
4. 정렬된 두 부분 리스트를 병합하여 전체 리스트를 정렬한다.

예제

정렬할 리스트: [38, 27, 43, 3, 9, 82, 10]

1. 분할 단계:
   • [38, 27, 43, 3]와 [9, 82, 10]으로 분할
   • 다시 각각을 [38, 27]과 [43, 3], [9, 82]와 [10]으로 분할
   • 계속 분할하여 [38], [27], [43], [3], [9], [82], [10]이 된다.
2. 정복 및 병합 단계:
   • [38]과 [27]을 병합하여 [27, 38]
   • [43]과 [3]을 병합하여 [3, 43]
   • [9]과 [82]을 병합하여 [9, 82]
   • [10]은 그대로 유지
   • [27, 38]과 [3, 43]을 병합하여 [3, 27, 38, 43]
   • [9, 82]과 [10]을 병합하여 [9, 10, 82]
   • 최종적으로 [3, 27, 38, 43]과 [9, 10, 82]을 병합하여 [3, 9, 10, 27, 38, 43, 82]

시간 복잡도

병합 정렬의 시간 복잡도는 최선, 평균, 최악의 경우 모두 O(n log n)이다. 이는 병합 정렬이 항상 리스트를 반으로 나누고, 각 단계에서 병합하는 과정이 O(n)이기 때문이다.

공간 복잡도

병합 정렬은 O(n)의 추가 메모리를 필요로 한다. 이는 병합 단계에서 새로운 리스트를 생성하여 요소를 저장하기 때문이다.

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

    left_sort = merge_sort(left)
    right_sort = merge_sort(right)

    return merge(left_sort, right_sort)

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

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

    new_arr.extend(left[i:])
    new_arr.extend(right[j:])

    return new_arr

arr = [38, 27, 43, 3, 9, 82, 10]
sorted_arr = merge_sort(arr)
print("Sorted array is:", sorted_arr)

 

모든 코드는 github에 저장되어 있습니다.

https://github.com/SeongUk18/Algorithm/tree/main/Data_structure_algorithms