토픽 13 / 82

팀 정렬 (TimSort)

병합 정렬과 삽입 정렬을 결합한 하이브리드 안정 정렬 알고리즘으로, 실제 데이터의 부분 정렬 패턴을 활용하여 최적화하며 Python과 Java의 기본 정렬로 채택

목적: 실세계 데이터에 최적화된 고성능 안정 정렬

특징: 하이브리드(병합+삽입), 안정 정렬, 적응형(Adaptive), Run 기반

Run 탐지: 입력에서 이미 정렬된 부분 수열(Run)을 탐지하여 활용, 최소 Run 크기(minrun, 보통 32~64)보다 짧으면 삽입 정렬로 확장

병합 전략: Run들을 스택에 쌓고, 크기 균형 규칙(|A| > |B| + |C|, |B| > |C|)에 따라 병합, 불균형 병합 방지

갤러핑 모드(Galloping Mode): 병합 시 한쪽 Run에서 연속으로 원소가 선택되면 이진 탐색으로 전환하여 복사량 최소화

시간 복잡도: 최선 O(n)(이미 정렬), 평균/최악 O(n log n)

공간 복잡도: O(n) - 병합용 임시 배열

장점: 안정 정렬, 부분 정렬 데이터에 매우 빠름, 최악에도 O(n log n) 보장

단점: 추가 메모리 O(n), 구현 복잡, 작은 배열에서는 삽입 정렬과 유사

적용사례: Python list.sort()/sorted(), Java Arrays.sort(Object[]), Android, Swift

비교: TimSort(안정/적응형/O(n log n)) vs 퀵(불안정/빠름/최악 O(n²)) vs 병합(안정/항상 O(n log n)/적응 없음)

연관: 병합 정렬, 삽입 정렬, 안정 정렬, Run, 갤러핑