정의
팀소트(Timsort)는 실세계 데이터에 대해 높은 효율성을 보이도록 설계된 하이브리드형 안정 정렬 알고리즘이다. 병합 정렬(Merge Sort)과 삽입 정렬(Insertion Sort)의 장점을 결합한 형태이며, 파이썬 표준 라이브러리의 list.sort()와 sorted() 함수, 자바 SE 7 이후의 Arrays.sort() 등 여러 프로그래밍 언어에서 기본 정렬 알고리즘으로 채택되고 있다.
개요
팀소트는 2002년 파이썬 개발자 팀 피터스(Tim Peters)가 파이썬 2.3 버전부터 적용하기 위해 구현하였다. 알고리즘은 입력 배열을 순차적으로 탐색하면서 이미 정렬된 연속 구간(‘run’)을 식별하고, 이러한 구간들을 스택에 저장한다. 스택에 저장된 구간들 중 일정한 병합 조건을 만족하면 상위 구간들을 병합해 나가며 전체 데이터를 정렬한다. 삽입 정렬은 작은 구간에 대해 빠른 정렬을 제공하고, 병합 정렬은 큰 구간에 대해 안정적인 O(n log n) 시간 복잡도를 유지한다.
어원/유래
‘팀소트(Timsort)’라는 명칭은 알고리즘을 고안한 팀 피터스(Tim Peters)의 이름에서 유래한다. ‘Tim’ + ‘sort’의 결합 형태이며, 공식적인 약어는 존재하지 않는다.
특징
| 특징 | 내용 |
|---|---|
| 안정성 | 동일한 키 값을 가진 원소들의 상대 순서를 유지한다(Stable Sort). |
| 시간 복잡도 | 최선·평균·최악 모두 O(n log n)이며, 실제 데이터에서 작은 ‘run’이 많이 존재할 경우 삽입 정렬 단계가 주도하여 더 빠르게 동작한다. |
| 공간 복잡도 | 추가적인 보조 배열을 사용하여 O(n) 공간을 요구한다. |
| 실제 데이터 최적화 | 자연스럽게 정렬된 구간(‘run’)을 활용함으로써, 거의 정렬된 데이터에 대해 매우 높은 성능을 보인다. |
| 광범위한 채택 | 파이썬(2.3 이후), 자바(7 이상), 스칼라, 루비 등 다양한 언어와 라이브러리에서 기본 정렬 메커니즘으로 채택되고 있다. |
| 구현 방식 | 삽입 정렬을 이용한 ‘run’ 확장, 스택 기반 병합 정책, 최소·최대 ‘run’ 길이 조정(기본 32~64) 등으로 구성된다. |
관련 항목
- 병합 정렬(Merge Sort) – 팀소트가 기반으로 사용하는 분할·정복 방식의 정렬 알고리즘.
- 삽입 정렬(Insertion Sort) – 작은 구간에 대해 팀소트가 활용하는 정렬 방법.
- 안정 정렬(Stable Sort) – 정렬 후에도 동일 키 값 원소의 순서를 보존하는 정렬 알고리즘의 특성.
- 파이썬 표준 라이브러리 –
list.sort()와sorted()함수에서 팀소트를 사용. - 자바 표준 라이브러리 –
Arrays.sort()와Collections.sort()에서 팀소트를 기본 구현으로 채택.
※ 본 내용은 위키백과 및 공식 문서 등을 기반으로 작성되었으며, 확인되지 않은 정보는 포함하지 않았다.