[정글 베이직 14] — 머지 정렬 (Merge Sort)

 

📋 문제 소개

문제 설명

머지 정렬(Merge Sort) 알고리즘을 구현한다. 배열을 절반으로 나누고, 각각을 정렬한 후 두 포인터로 병합한다.

INPUT

정렬되지 않은 정수 배열 arr

OUTPUT

오름차순으로 정렬된 배열

예제

입력

arr = [38, 27, 43, 3, 9, 82, 10]

출력

[3, 9, 10, 27, 38, 43, 82]

💡 힌트

배열을 절반으로 분할(재귀) → 각 부분 정렬 → 정렬된 두 부분을 병합.

① 문제 이해

항목	내용
문제	머지 정렬로 배열을 오름차순 정렬한다.
특징	안정 정렬(Stable Sort), 항상 O(n log n) 보장
예제	[38,27,43,3,9,82,10] → [3,9,10,27,38,43,82]

② 핵심 아이디어

반으로 나누고 → 각각 재귀 정렬 → 두 정렬된 배열을 두 포인터로 병합한다.

# 수도코드
merge_sort(arr, left, right):
    if left >= right: return
    mid = (left+right)//2
    merge_sort(arr, left, mid)       # 왼쪽 정렬
    merge_sort(arr, mid+1, right)    # 오른쪽 정렬
    merge(arr, left, mid, right)     # 병합

merge(arr, left, mid, right):
    left_arr  = arr[left:mid+1]      # 왼쪽 복사
    right_arr = arr[mid+1:right+1]   # 오른쪽 복사
    두 포인터로 비교하며 arr에 복사
    남은 원소 복사

③ 코드 분석

def merge(arr, left, mid, right):
    left_arr  = arr[left:mid + 1]     # ① 왼쪽 임시 복사
    right_arr = arr[mid + 1:right + 1] # ② 오른쪽 임시 복사
    i, j, k = 0, 0, left

    while i < len(left_arr) and j < len(right_arr):
        if left_arr[i] <= right_arr[j]:   # ③ 작은 값 먼저
            arr[k] = left_arr[i]; i += 1
        else:
            arr[k] = right_arr[j]; j += 1
        k += 1

    while i < len(left_arr):              # ④ 왼쪽 잔여
        arr[k] = left_arr[i]; i += 1; k += 1
    while j < len(right_arr):             # ⑤ 오른쪽 잔여
        arr[k] = right_arr[j]; j += 1; k += 1

def merge_sort_helper(arr, left, right):
    if left < right:
        mid = (left + right) // 2
        merge_sort_helper(arr, left, mid)
        merge_sort_helper(arr, mid + 1, right)
        merge(arr, left, mid, right)      # ⑥ 병합

번호	코드	의미
①②	임시 배열 복사	원본 덮어쓰기 전에 원본 값을 안전하게 보관
③	<=	<= 로 안정 정렬 보장 (같은 값이면 왼쪽을 먼저 넣음)
④⑤	잔여 원소 복사	둘 중 한 배열이 먼저 소진되면 나머지를 그대로 복사
⑥	merge() 위치	두 재귀 호출 이후에 병합 — 순서가 바뀌면 안 된다

④ 자주 하는 실수

⚠️ 잔여 원소 복사 누락

두 포인터 while 루프가 끝나도 한쪽에 원소가 남아 있을 수 있다. ④⑤의 잔여 복사 루프를 빠뜨리면 일부 원소가 사라진다.

⚠️ 퀵정렬과의 차이 혼동

머지 정렬은 나누는 것이 먼저, 병합이 마지막이다. 퀵정렬은 partition(피벗 정렬)이 먼저다.

💡 퀵정렬 vs 머지정렬: 퀵정렬은 평균 빠르지만 최악 O(n²). 머지정렬은 항상 O(n log n)이지만 O(n) 추가 메모리 필요. 어느 게 낫냐? 상황에 따라 다르다.

⑤ 시간복잡도

항목	값	이유
시간	O(n log n)	log n 깊이 × 각 레벨에서 O(n) 병합
공간	O(n)	임시 배열(left_arr, right_arr) 전체 크기 합 = n

⑥ 핵심 정리

• 분할 → 재귀 정렬 → 병합 순서. merge()는 항상 재귀 이후.
• 임시 배열에 먼저 복사하고 원본에 덮어쓴다 — 순서 바꾸면 데이터 손실.
• 잔여 원소 복사 루프(while i < len(...)) 반드시 포함.
• 안정 정렬이 필요한 상황(같은 값의 순서 유지)엔 머지 정렬을 선택하자.