합병 정렬

8.1 합병 정렬의 정의

합병 정렬 (Merge Sort)은 효율적이고, 안정적이며 비교 기반의 정렬 알고리즘으로, "분할 정복" 접근 방식을 사용하여 요소를 정렬한다. 알고리즘은 배열을 두 부분으로 나누고, 각각의 부분을 재귀적으로 정렬한 다음 정렬된 부분들을 하나의 정렬된 배열로 합친다.

작동 원리:

분할:

• 원래 배열을 반으로 나누어 두 개의 하위 배열을 만든다.
• 각 하위 배열이 하나의 요소(또는 비어있는 배열)가 될 때까지 이 과정을 반복한다.

병합:

• 두 인접한 하위 배열을 하나의 정렬된 배열로 합친다.
• 하나의 정렬된 배열이 나올 때까지 병합 과정을 반복한다.

합병 정렬의 시간 및 공간 복잡도

시간 복잡도:

• 최악의 경우: O(n log n)
• 평균의 경우: O(n log n)
• 최선의 경우: O(n log n)

공간 복잡도:

O(n) — 임시 하위 배열을 저장하기 위한 추가 메모리가 필요하다.

8.2 하향식 합병 방법

원래 시퀀스는 재귀적으로 반으로 나누어지며, 하나의 요소까지 하위 시퀀스를 얻을 때까지 계속된다. 얻어진 하위 시퀀스에서 병합 방법으로 정렬된 쌍을 형성하고, 그런 식으로 정렬된 4개 쌍, 등등을 만들어간다.

시퀀스를 살펴보자:

시퀀스를 두 부분으로 분할한다 (재귀적으로, 쌍이 나올 때까지).

각 하위 시퀀스를 병합 방법으로 정렬하여 완성된 시퀀스를 얻는다.

8.3 합병 정렬 알고리즘 구현

여기에서 우리가 사용할 것은 재귀야! 이전의 것들과 비교했을 때 정말 좋은 빠른 알고리즘이지. 이 알고리즘은 배열을 반으로 나누고, 각 부분을 따로 정렬한 후, 정렬된 부분들을 빠르게 합친다.

그 구현은 대략 이렇게 생겼어:

def merge_sort(arr):
    if len(arr) > 1:
        mid = len(arr) // 2  # 배열의 중간을 찾는다
        left_half = arr[:mid]  # 배열을 두 하위 배열로 나눈다
        right_half = arr[mid:]
        
        merge_sort(left_half)  # 왼쪽 부분을 재귀적으로 정렬한다
        merge_sort(right_half)  # 오른쪽 부분을 재귀적으로 정렬한다
        
        i = j = k = 0
        
        # 정렬된 부분을 병합한다
        while i < len(left_half) and j < len(right_half):
            if left_half[i] < right_half[j]:
                arr[k] = left_half[i]
                i += 1
            else:
                arr[k] = right_half[j]
                j += 1
            k += 1
        
        # 남은 요소에 대한 체크
        while i < len(left_half):
            arr[k] = left_half[i]
            i += 1
            k += 1
        
        while j < len(right_half):
            arr[k] = right_half[j]
            j += 1
            k += 1
    return arr

# 사용 예시:
arr = [38, 27, 43, 3, 9, 82, 10]
sorted_arr = merge_sort(arr)
print("정렬된 배열:", sorted_arr)
# 출력: 정렬된 배열: [3, 9, 10, 27, 38, 43, 82]

핵심은 처음에 있어:

def merge_sort(arr):
    if len(arr) > 1:
        mid = len(arr) // 2 # 배열의 중간을 찾는다
        left_half = arr[:mid] # 배열을 두 하위 배열로 나눈다 right_half = arr[mid:]
        
        merge_sort(left_half)  # 왼쪽 부분을 재귀적으로 정렬한다
        merge_sort(right_half)  # 오른쪽 부분을 재귀적으로 정렬한다

여기서 이렇게 작동해:

1. 우리는 배열의 중간을 찾는다
2. 배열을 2개로 나눈다
3. 각 부분을 따로 정렬한다

이런 접근 방식이 알고리즘을 크게 가속화해.