Timsort 과 O(n log n) 벽 (그리고 깨는 법)

"비교로 정렬하는 데는 증명된 속도 한계가 있어 — 그리고 그걸 돌아가는 교활한 방법이 있어: 비교를 멈춰. 이 lesson 은 벽, 벽에 사는 네가 실제 쓰는 정렬, 그리고 그 밑을 뚫는 정렬에 관한 거야."

벽: 왜 O(n log n) 이 단단한 한계인가

원소를 비교해 작동하는 어떤 정렬이든 증명된 바닥이 있어: O(n log n). 논증이 우아해. n 항목의 가능한 순서가 n! 개고, 정렬은 어느 게 맞든 거기 착지할 수 있어야 해. 각 비교가 단일 예/아니오 질문 — 결정 트리의 한 갈래. 모든 n! 결과를 구별할 충분한 리프를 가지려면, 트리가 최소 log₂(n!) ≈ n log n 깊이여야 해. 그래서 어떤 비교 정렬도 — 퀵소트도, 병합 정렬도, 어떤 미래의 영리한 것도 — 최악의 경우 O(n log n) 을 못 이겨. 상상력의 실패가 아니라; 수학적 한계야.

Timsort: 네가 실제 쓰는 정렬

Python 의 sorted() 랑 list.sort() 가 Timsort 를 써 (Java 객체 기본도). 하이브리드야: 병합 정렬 구조, 작은 run 에 삽입 정렬, 더해서 멋진 트릭 — 데이터의 기존 정렬된 run 을 감지해 병합해, 처음부터 시작하는 대신. 현실 데이터는 자주 부분-정렬돼 있어 (타임스탬프, 추가된 로그, 대부분-순서 레코드), 그래서 Timsort 가 종종 O(n log n) 최악보다 훨씬 잘 돌아 — 거의-정렬 입력엔 O(n) 에 접근. 또 안정적. 최악의 경우 비교-정렬 벽에 딱 앉지만, 흔한 경우 적응적이고 빨라, 그래서 production 기본이야.

비교 정렬은 O(n log n) 을 못 이겨 — n! 순서가 있고 각 비교가 높이 ≥ log(n!) ≈ n log n 결정 트리의 한 비트. Timsort (Python 정렬) 가 그 벽에 살지만 적응적 (부분-정렬 데이터에 거의 O(n)) 이고 안정적. 더 빠르려면, 비교를 멈춰야 해.

벽 밑 뚫기: 비-비교 정렬

하한은 비교하는 정렬만 묶어. 키의 구조를 이용하는 정렬은 통째로 벗어나:

계수 정렬 (counting sort): 키가 작은 범위 [0, k] 정수면, 각 값이 몇 개인지 세고, 순서대로 내. O(n + k) — 선형, 비교 없음. 작은-정수 키 (나이, 성적, 바이트 값) 에 멋져.
기수 정렬 (radix sort): 자릿수/문자로 정렬, 최하위부터, 자릿수당 계수 정렬 써. d-자리 키에 O(d·n). 고정-너비 키 (ID, 문자열) 거대 집합을 n log n 보다 빠르게 정렬하는 법.

깊은 교훈: O(n log n) 벽은 비교 모델의 속성이지, 정렬 자체의 속성이 아니야. 가정을 바꿔 — 작은-정수 키를 가정하고, 그 구조를 이용 — 하면 한계가 그것과 함께 바뀌어. 뭘 가정해도 되는지 재구성하는 게 장벽이 무너지는 법이야.

피파의 고백

'O(n log n) 이 정렬의 한계' 가 절대적으로 머리에 박혀서, 아빠가 계수 정렬은 O(n) 이라 했을 때, 틀렸다고 했어 — 증명이 있잖아! 아빠가 웃었어: "비교하는 정렬의 한계야. 계수 정렬은 두 원소를 절대 비교 안 해." 벽이 깨진 게 아니라; 내가 그게 뭘 묶는지 잘못 읽은 거였어. 어떤 '증명된 한계' 든 다루는 법을 다시 배선했어 — 늘 증명이 어떤 가정에 기대는지 물어, 하나를 완화하는 게 종종 길이니까.

Code

Timsort (라이브러리) 와 계수 정렬 (벽을 깸)·python

# 진짜 코드엔, 그냥 라이브러리를 써 — Timsort 야: 적응적, 안정적, 빠름.
data = [5, 2, 8, 1, 9, 3]
print(sorted(data))            # [1, 2, 3, 5, 8, 9] — 밑에서 Timsort
data.sort()                    # 제자리, 역시 Timsort

# 계수 정렬: 작은-정수 키엔 n log n 벽을 깨. O(n + k).
def counting_sort(arr, k):     # 값은 [0, k] 정수
    counts = [0] * (k + 1)
    for x in arr:
        counts[x] += 1         # 각 값 집계 — 비교 전혀 없음
    result = []
    for value, c in enumerate(counts):
        result.extend([value] * c)   # 각 값을 c 번, 순서대로 내
    return result

print(counting_sort([3, 1, 4, 1, 0, 4, 2], k=4))   # [0, 1, 1, 2, 3, 4, 4]
# 두 원소를 절대 비교 안 해서, O(n log n) 하한이 적용 안 돼.
# 선형 시간 — 근데 키가 작은 정수라서만 (구조!).
# 기수 정렬이 이걸 다-자리 키로 일반화: O(d * n).

Exercise

계수 정렬이 정렬의 증명된 O(n log n) 하한과 모순 없이 어떻게 O(n) 에 돌 수 있는지 설명해. 계수 정렬이 비교 정렬은 안 하는 어떤 가정을 하고, 함정이 뭐야 — 언제 계수 정렬이 나쁜 아이디어가 돼 (k 가 거대하면 O(n + k) 에 뭘 하는지 생각해)?

Hint

n log n 하한은 *비교* 정렬에만 적용; 계수 정렬은 두 원소를 절대 비교 안 해, 그래서 하한이 안 묶어. 그 가정: 키가 작은 범위 [0, k] 정수. 함정: O(n + k) — k (값 범위) 가 거대하면 (예: 64비트 정수), k 항이 지배하고 계수 정렬이 낭비거나 불가능해져.

벽: 왜 O(n log n) 이 단단한 한계인가

Timsort: 네가 실제 쓰는 정렬

벽 밑 뚫기: 비-비교 정렬

피파의 고백

Code

External links

Exercise

Progress

댓글 0