[알고리즘/정렬] 병합 정렬

0. 🔖 목차

1. 병합 정렬 알고리즘
   1-1. 개념
   1-2. 알고리즘
   1-3. 복잡도

1. 병합 정렬 알고리즘

1-1. 개념

병합 정렬(Merge Sort)은 분할 정복(divide and conquer) 전략을 사용하는 비교 기반 정렬 알고리즘이다.

일반적으로 두 부분으로 나누어 각각을 재귀적으로 정렬한 다음, 두 정렬된 리스트를 합병하여 최종적으로 정렬된 리스트를 얻는 방식으로 작동한다.

1. 리스트의 길이가 1 이하이면 이미 정렬된 것으로 본다. 그렇지 않은 경우에는
2. 분할(divide): 정렬되지 않은 리스트를 절반으로 잘라 비슷한 크기의 두 부분 리스트로 나눈다.
3. 정복(conquer): 각 부분 리스트를 재귀적으로 합병 정렬을 이용해 정렬한다.
4. 결합(combine): 두 부분 리스트를 다시 하나의 정렬된 리스트로 합병한다. 이때 정렬 결과가 임시배열에 저장된다.
5. 복사(copy): 임시 배열에 저장된 결과를 원래 배열에 복사한다.

1-2. 알고리즘

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 = []
    left_index, right_index = 0, 0

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

    if left_index < len(left):
        sorted_arr.extend(left[left_index:])
    if right_index < len(right):
        sorted_arr.extend(right[right_index:])

    return sorted_arr

1-3. 복잡도