Algorithm Guidecomplexity: O(n log n)

병합 정렬 (Merge Sort)

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

01 알고리즘 작동 원리 탐색

Interactive Step-by-Step

HOVER OR SCROLL

Merge Sort

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

Logic Node1 / 45

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

02 쉽게 이해하기

For Everyone

🔑비유

반으로 계속 나눈 뒤, 정렬된 조각들을 지퍼처럼 끼워 합치는 것.

💡쉽게 말하면

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

항상 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