Algorithm Guidecomplexity: O(n log n)

병합 정렬 (Merge Sort)

배열을 더 이상 나눌 수 없을 때까지 나눈 후, 정렬하면서 다시 병합하는 안정적이고 일관된 성능을 가진 분할 정복 알고리즘입니다.

01병합 정렬 (Merge Sort)

알고리즘 작동 원리 탐색

병합 정렬을 시작합니다. 배열을 더 이상 나눌 수 없을 때까지 절반으로 나눕니다.

배열을 앞뒤 절반으로 가릅니다. 38·27·43과 10·76·15 두 덩이입니다.

왼쪽 덩이를 다시 38·27과 43으로 가릅니다.

38·27도 한 칸씩으로 갈라 놓습니다.

값이 하나만 남은 38은 그 자체로 정렬된 상태입니다.

27도 마찬가지입니다. 더 나눌 수 없으니 이제 합칠 차례입니다.

갈라 두었던 38과 27을 다시 합칩니다.

양쪽 맨 앞의 38과 27을 견줍니다. 27이 더 작으니 먼저 나갑니다.

27을 앞자리에 내려놓습니다.

한쪽이 비었으니 남은 38을 그대로 이어 붙입니다.

혼자 남아 있던 43도 정렬된 상태입니다.

정리된 27·38에 43을 합쳐 왼쪽 절반을 완성합니다.

맨 앞의 27과 43을 견줍니다. 27이 더 작습니다.

27을 앞자리에 내려놓습니다.

다음은 38과 43입니다. 이번에도 왼쪽이 더 작습니다.

38을 그다음 자리에 내려놓습니다.

왼쪽이 비었으니 남은 43을 이어 붙입니다. 왼쪽 절반이 27·38·43으로 정렬됐습니다.

이제 오른쪽 덩이 차례입니다. 10·76과 15로 가릅니다.

10·76도 한 칸씩으로 갈라 놓습니다.

10은 더 나눌 수 없습니다.

76도 마찬가지입니다. 이제 둘을 합칩니다.

갈라 두었던 10과 76을 합칩니다.

맨 앞의 10과 76을 견줍니다. 10이 더 작습니다.

10을 앞자리에 내려놓습니다.

남은 76을 이어 붙입니다.

혼자 남아 있던 15도 정렬된 상태입니다.

정리된 10·76에 15를 합쳐 오른쪽 절반을 완성합니다.

맨 앞의 10과 15를 견줍니다. 10이 더 작습니다.

10을 앞자리에 내려놓습니다.

다음은 76과 15입니다. 이번에는 오른쪽이 더 작습니다.

15를 그다음 자리에 내려놓습니다.

남은 76을 이어 붙입니다. 오른쪽 절반도 10·15·76으로 정렬됐습니다.

정렬된 두 절반을 마지막으로 합칩니다. 양쪽 맨 앞만 견주면 됩니다.

27과 10을 견줍니다. 오른쪽이 더 작습니다.

10을 맨 앞자리에 내려놓습니다.

27과 15를 견줍니다. 또 오른쪽이 더 작습니다.

15를 그다음 자리에 내려놓습니다.

27과 76을 견줍니다. 이번에는 왼쪽이 더 작습니다.

27을 그다음 자리에 내려놓습니다.

38과 76을 견줍니다. 여전히 왼쪽이 더 작습니다.

38을 그다음 자리에 내려놓습니다.

43과 76을 견줍니다. 왼쪽의 마지막 값이 더 작습니다.

43을 그다음 자리에 내려놓습니다.

왼쪽이 모두 나갔습니다. 남은 76을 맨 끝에 놓습니다.

병합 정렬이 끝났습니다. 나눌 때가 아니라 합칠 때 순서가 정해지는 정렬입니다.

Live Python

1def merge_sort(arr, low, high):

# low: 0, high: 5

2 if low < high:

3 mid = low + (high - low) // 2

4 merge_sort(arr, low, mid)

5 merge_sort(arr, mid + 1, high)

6 merge(arr, low, mid, high)

8def merge(arr, low, mid, high):

9 L = arr[low:mid+1]

10 R = arr[mid+1:high+1]

11 i = j = 0

12 k = low

13 while i < len(L) and j < len(R):

14 if L[i] <= R[j]:

15 arr[k] = L[i]

16 i += 1

17 else:

18 arr[k] = R[j]

19 j += 1

20 k += 1

21 while i < len(L):

22 arr[k] = L[i]

23 i += 1

24 k += 1

25 while j < len(R):

26 arr[k] = R[j]

27 j += 1

28 k += 1

1 / 45

02 쉽게 이해하기

For Everyone

🔑핵심 동작

반으로 나누기를 반복한 뒤, 정렬된 조각 둘을 앞에서부터 견주며 합칩니다. 어떤 입력에도 O(n log n) 입니다.

💡쉽게 말하면

배열을 절반씩 쪼개 각각 정렬하고, 두 정렬된 조각을 차례로 합칩니다.

항상 O(n log n)이고 안정 정렬이에요.

📍어디에 쓰나

–안정성이 필요한 정렬
–외부 정렬(대용량 파일)

03 파이썬 구현 코드

병합 정렬 (Merge Sort)의 핵심 로직을 담은 표준 구현 예시입니다. 가급적 간결하고 읽기 쉬운 코드로 작성되었습니다.

core_implementation.py

def merge_sort(arr, low, high):
    if low < high:
        mid = low + (high - low) // 2
        merge_sort(arr, low, mid)
        merge_sort(arr, mid + 1, high)
        merge(arr, low, mid, high)

def merge(arr, low, mid, high):
    L = arr[low:mid+1]
    R = arr[mid+1:high+1]
    i = j = 0
    k = low
    while i < len(L) and j < len(R):
        if L[i] <= R[j]:
            arr[k] = L[i]
            i += 1
        else:
            arr[k] = R[j]
            j += 1
        k += 1
    while i < len(L):
        arr[k] = L[i]
        i += 1
        k += 1
    while j < len(R):
        arr[k] = R[j]
        j += 1
        k += 1