Algorithm Guidecomplexity: O(n log n)

Merge Sort

A stable divide-and-conquer algorithm with consistent performance: split the array until indivisible, then merge back while sorting.

01 Explore How It Works

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 Understand It Simply

For Everyone

🔑Analogy

Keep halving, then zip the sorted pieces back together.

💡In Plain Words

Splits the array in halves, sorts each, and merges two sorted pieces in order.

Always O(n log n) and stable.

📍Where It's Used

–Sorting that needs stability
–external sorting of large files

03 Python Implementation

A clean, readable reference implementation of the core logic of 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