Timsort의 run 병합 전략과 안정 정렬 특성
Timsort의 run 탐지, minrun 확장, 스택 병합 불변식과 갤로핑 모드를 실무 정렬 관점에서 정리한다.
2026-08-14 · 최초 발행 2024-04-29
부분 정렬 상태를 run으로 활용하는 방식
Timsort는 Insertion sort와 Merge sort를 결합한 안정 정렬 알고리즘이다. 입력에서 이미 정렬되어 있는 증가·감소 구간인 run을 찾아 활용하고, 짧은 구간은 이진 삽입 정렬로 보완한 뒤 병합한다.
이미 정렬된 입력에서는 run 탐지 효과로 최선 O(n)에 도달할 수 있다. 평균과 최악 시간복잡도는 모두 O(n log n)이며, 같은 키를 가진 원소의 상대 순서도 보존한다. 병합에는 임시 버퍼가 필요하므로 최악에는 O(n) 수준의 추가 메모리를 사용하지만, 실제 사용량은 병합 단위에 비례해 감소하는 경향이 있다.
run을 정규화하고 병합 순서를 제어한다
입력 배열에서 단조 증가 또는 감소 구간을 찾는다. 감소 run은 순서를 반전해 증가 run으로 정규화한다. run이 minrun보다 짧으면 이진 삽입 정렬로 길이를 확장해 이후 병합 비용을 조정한다. minrun은 일반적으로 32~64 사이에서 데이터 크기를 기준으로 산출한다.
확정된 run은 스택에 쌓인다. 이때 인접 run의 길이 사이에 A > B + C, B > C 같은 불변식을 유지하며, 조건이 깨지면 인접 run을 즉시 병합한다. 짧은 run이 스택 깊숙이 누적되는 일을 막아 병합 횟수와 높이를 제한하고 최악 성능을 보장하기 위한 장치다.
병합 중 한쪽 run의 우세가 길게 이어지면 이진 탐색 기반 galloping 모드로 전환할 수 있다. 다수의 원소를 한 번에 이동해 비교 횟수를 줄이고 지역성을 활용한다.
처리 흐름
입력은 배열, 선택 가능한 비교 함수, minrun 파라미터다. run 탐지와 정규화, minrun 확장, 스택 불변식에 따른 병합, galloping 전환을 거쳐 안정 정렬된 배열을 출력한다.
비교할 수 없는 요소가 섞이면 예외가 발생할 수 있다. 임시 버퍼를 할당하지 못할 가능성도 있으며, NaN처럼 비총서 관계를 갖는 값의 처리 정책은 별도로 확인해야 한다.
안정적인 정렬 순서가 필요한 작업
부분 정렬 상태가 자주 남는 업무 로그, 타임스탬프 기반 레코드, 증분 정렬 시나리오에서 run 활용이 의미를 가질 수 있다. UI 리스트의 다중 컬럼 정렬이나 보고서·청구서 정렬 파이프라인처럼 같은 키의 상대 순서를 유지해야 하는 경우에도 안정 정렬 특성이 맞는다.
카테고리나 상태 코드처럼 키 중복이 많은 데이터에서는 병합 정렬의 대안으로 볼 수 있다. Python의 list.sort와 sorted, Java의 Collections.sort 및 객체 배열 정렬, Android 플랫폼 정렬, V8의 Array.sort 안정화 구현에도 Timsort 또는 Timsort 계열 기법이 채택되거나 활용된다. Chrome V8의 세부 구현은 버전에 따라 다르며 최신 정보 확인이 필요하다.
운영 전에는 비교 함수의 반사성·추이성·반대칭성을 검증해야 한다. NaN, null, 서로 다른 타입이 섞인 데이터의 정책도 정하고, 대용량 입력에서는 임시 버퍼의 메모리 상한과 모니터링을 구성한다. 배치나 증분 처리 단계에서 부분 정렬 상태를 유지하는 전략도 함께 검토할 수 있다.
부분 정렬 비율이 높을수록 비교와 이동 횟수가 크게 줄어들며, 최선 O(n) 달성이 가능하다. 무작위 데이터에서도 평균 O(n log n)을 유지한다. 안정 정렬은 후속 파이프라인 결과의 일관성을 확보하고, 최악 O(n log n) 보장은 SLA 수립을 돕는다. 병합 단위별 임시 버퍼 사용은 평균 메모리 사용량을 줄이는 경향이 있으며, 표준 라이브러리 채택은 운영·검증 비용을 축소한다.
정량 지표는 입력 분포·하드웨어·런타임 구현에 따라 상이. 벤치마크 사전 검증 권장, 최신 정보 확인 필요
다른 범용 정렬과의 차이
| 알고리즘 | 성능(평균/최악) | 확장성(부분 정렬/대용량) | 일관성(안정 정렬) | 안정성(최악 보장) | 운영 편의(메모리/채택) |
|---|---|---|---|---|---|
| Timsort | O(n log n) / O(n log n) | 부분 정렬 강점 높음 / 대용량 양호 | 예 | 예 | 가변 O(n) 버퍼 / 다수 표준 채택 |
| Merge sort | O(n log n) / O(n log n) | 부분 정렬 영향 적음 / 대용량 양호 | 예 | 예 | O(n) 버퍼 / 구현 단순 |
| Quicksort(Introsort) | O(n log n) / O(n log n) | 부분 정렬 이점 제한 / 대용량 우수 | 아니오(일반) | 예(Introsort) | O(log n) 스택 / 광범위 채택 |
| Heapsort | O(n log n) / O(n log n) | 부분 정렬 이점 제한 / 대용량 우수 | 아니오 | 예 | O(1) 추가 메모리 / 비교적 느림 |
표준 라이브러리 채택 범위
Python의 list.sort와 sorted는 기본 Timsort를 채택한다. Java SE 7+에서는 객체 배열과 Collections.sort에 Timsort를 채택하고, 기본형 배열에는 Dual-Pivot Quicksort를 사용한다. Android의 java.util 내부에는 TimSort 구현이 있다.
Chrome V8은 Array.prototype.sort의 안정 정렬화 과정에서 Timsort 계열 기법을 적용했으며, 세부 구현은 버전별로 다르므로 최신 정보 확인이 필요하다. Swift는 플랫폼과 버전에 따라 다르며, 표준 정렬의 안정성 보장 여부는 문서화 상태를 확인해야 한다.