Timsort의 자연 런과 안정 병합 전략

입력에 이미 있는 정렬 상태를 활용하는 방식

Timsort는 Insertion sort와 Merge sort를 결합한 하이브리드 정렬 알고리즘이다. 입력 배열에서 자연스럽게 정렬된 구간(run)을 먼저 찾고, 짧은 구간은 Insertion sort로 보강한 뒤 안정 병합으로 전체 순서를 맞춘다.

부분 정렬된 데이터나 동일 키가 많은 데이터에서 적응하도록 설계됐으며, Python 표준 정렬을 출발점으로 Java SE 7, Android 등에도 확산됐다. Python, Java SE 7(객체 배열), Android, 일부 엔진·언어(V8, Swift 등)에서 사용 보고가 있으나 최신 정보 확인이 필요하다.

시간 복잡도는 거의 정렬된 입력에서 최선 O(n), 평균과 최악에서 O(n log n)이다. 보조 공간은 최악 O(n)이지만, 일반적으로는 병합 시 작은 런 크기 수준의 메모리를 사용해 Merge sort 대비 평균 추가 메모리 사용량을 낮춘다.

런을 발견하고 필요한 길이까지 보강한다

배열을 선형으로 훑으며 연속된 오름차순 또는 내림차순 구간을 찾는다. 내림차순 런은 반전해 오름차순 런으로 통일한다.

탐지한 런이 minrun보다 짧으면 이진 삽입 정렬로 길이를 확장한다. minrun은 통상 32~64이며, 작은 구간에서의 캐시 지역성과 상수항 이점을 활용하는 선택이다.

런 스택이 병합 순서를 제한한다

발견한 런은 스택에 쌓인다. 상위 2~3개 런의 길이가 X > Y + Z 및 Y > Z와 유사한 불변식 조건을 만족하지 못하면 즉시 병합한다.

이 제어는 Fibonacci 유사 길이 분포를 유도한다. 그 결과 병합 깊이를 제한하고 최악 시간·공간 사용량을 관리할 수 있다.

안정 병합과 갈로핑의 역할

병합은 안정적으로 수행되므로 동일 키의 상대 순서가 보존된다. 2차 키의 순서가 남아야 하는 후속 처리에서는 이 특성이 직접적인 의미를 갖는다.

한 런이 연속해서 우세한 상황에서는 지수 탐색과 이진 탐색을 사용하는 갈로핑 모드가 동작한다. 긴 구간의 전송을 묶어 처리해 비교와 복사 횟수를 줄이는 방식이다.

병합 시에는 작은 쪽 런 크기만큼의 임시 버퍼를 사용한다. 전체 O(n) 최악 공간 복잡도는 유지하지만 낮은 상수로 운용하며, 작은 런 확장에 Insertion sort를 쓰는 점도 L1/L2 캐시 적중률 개선에 기여한다.

정렬 작업에서의 선택 기준

애플리케이션에서는 테이블·리스트 UI의 페이징 정렬이나 로그·이벤트 스트림의 기간별 정렬에 사용할 수 있다. 서버 측 배치 후처리에서 거의 정렬된 파티션을 다루거나, 키-값 묶음의 2차 키를 유지해야 할 때도 안정 정렬의 장점이 드러난다.

데이터 처리 파이프라인에서는 맵리듀스 전처리 단계의 메모리 내 정렬과 인덱스 빌드용 버퍼 정렬이 대상이 된다. 입력이 2050% 이상 부분 정렬된 경우 비교·이동 횟수가 체감되고, 워크로드에 따라 실측에서 1030% 처리시간 단축 사례가 존재한다. 평균 추가 메모리 사용량 감소는 GC와 메모리 압력을 완화하고 캐시 효율 개선으로도 이어진다.

지표	Timsort	Merge sort	Quicksort(Introsort)	Heapsort
성능(평균)	O(n log n), 부분 정렬에 매우 강함	O(n log n) 안정적	O(n log n) 상수항 유리	O(n log n) 상수항 큼
확장성(큰 n)	높음, 런 병합 깊이 제어	높음, 선형 병합	높음, 분할 균형 필요	높음
일관성(최악)	O(n log n) 보장	O(n log n) 보장	O(n^2) 가능(대응 필요)	O(n log n) 보장
안정성(Stable)	예	예	일반적 부정	부정
운영 편의(메모리)	평균 적음, 최악 O(n)	O(n)	O(log n) 보조(스택)	O(1)

주: Quicksort는 실무에서 보통 Introsort로 최악 방지. Timsort는 평균 추가 메모리 적으나 최악 O(n) 가능.

런 탐지부터 최종 병합까지

⤢✕

구현에서 확인할 조건

minrun은 n을 32~64 범위로 축소하면서 하위 비트를 누적하는 방식으로 선정하며, CPython 방식을 준용할 수 있다. 런 스택의 길이 관계가 불변식을 위반하면 바로 병합해야 한다. 조건이 잘못되면 최악 성능 저하나 버그를 유발할 수 있으며, 안드로이드 이슈 사례는 최신 정보 확인이 필요하다.

갈로핑 임계값은 경험적 기본 7이며 데이터 분포에 따라 상향·하향 튜닝할 수 있다. 병합용 임시 버퍼는 작은 런 크기만큼 1개를 재사용하고, 큰 n에서는 임시 버퍼 상한도 관리한다.

Python 3 개념 데모

# Python 3.11+, 교육용 축약 코드 (프로덕션용 아님)
def minrun(n: int) -> int:
    r = 0
    while n >= 64:
        r |= n & 1
        n >>= 1
    return n + r  # 32~64 사이

def find_run(a, lo, hi):
    if lo + 1 >= hi:
        return hi
    run_hi = lo + 1
    # 오름/내림 판정
    if a[run_hi] < a[lo]:
        while run_hi < hi and a[run_hi] < a[run_hi-1]:
            run_hi += 1
        a[lo:run_hi] = reversed(a[lo:run_hi])
    else:
        while run_hi < hi and a[run_hi] >= a[run_hi-1]:
            run_hi += 1
    return run_hi

def binary_insert(a, lo, hi):
    for i in range(lo+1, hi):
        x = a[i]
        l, r = lo, i
        while l < r:
            m = (l + r) // 2
            if a[m] <= x: l = m + 1
            else: r = m
        for j in range(i, l, -1):
            a[j] = a[j-1]
        a[l] = x

def timsort_skeleton(a):
    n = len(a)
    if n < 2: return a
    mr = minrun(n)
    runs = []
    i = 0
    while i < n:
        j = find_run(a, i, n)
        if j - i < mr:
            end = min(i + mr, n)
            binary_insert(a, i, end)
            j = end
        runs.append((i, j))
        # 스택 불변식 확인/병합은 생략(스켈레톤)
        i = j
    # 남은 런 병합 루프 생략
    return a

# 사용
data = [5,1,2,3,4,6,7,8]
print(timsort_skeleton(data[:]))  # 거의 정렬 데이터에서 선형에 근접

전제조건은 CPython 3.11+와 교육용 축약 구현이다. 상용 구현에는 스택 불변식, 안정 병합, 갈로핑을 반드시 포함해야 한다.

기본 선택지로 둘 수 있는 범위

자연 런 활용, Insertion 보강, 안정 병합, 불변식 제어, 갈로핑이 Timsort의 핵심이다. 일반 객체 정렬과 UI·배치 정렬에서는 기본 선택지로 검토할 수 있다. 매우 제한된 메모리 환경이나 단순 수치형 대량 정렬에서는 Introsort·Heapsort와의 트레이드오프를 함께 검토한다.