팀 정렬
팀 정렬은 입력에서 이미 정렬된 구간(run)을 찾아 병합하는 적응형 정렬이다 알고리즘의 적응형 안정 비교 정렬에 속하며, 데이터의 순서를 정하거나 특정 조건을 만족하는 값을 찾는 문제를 다룬다. 올바른 구현에서는 비교·키 표현과 알고리즘이 유지해야 하는 불변식을 먼저 정의한다.
| 분류 | 알고리즘 · 적응형 안정 비교 정렬 |
|---|---|
| 해결 문제 | 입력에서 이미 정렬된 구간(run)을 찾아 병합하는 적응형 정렬이다 |
| 핵심 동작 | 오름차순·내림차순 구간을 탐지하고 짧은 구간은 이진 삽입 정렬로 늘린다 |
| 시간 복잡도 | 최악 O(n log n) |
| 추가 공간 | 보조 버퍼 사용 |
| 주요 전제 | 안정적인 비교 연산과 run의 병합 버퍼가 필요하다 |
| 대표 활용 | Python·Java 등의 객체·배열 정렬 구현에 영향을 주었다 |
| 참고 자료 | MIT 강의 노트 |
팀 정렬은 입력에서 이미 정렬된 구간(run)을 찾아 병합하는 적응형 정렬이다 알고리즘의 적응형 안정 비교 정렬에 속하며, 데이터의 순서를 정하거나 특정 조건을 만족하는 값을 찾는 문제를 다룬다. 올바른 구현에서는 비교·키 표현과 알고리즘이 유지해야 하는 불변식을 먼저 정의한다.[1]
동작 원리는 다음과 같다. 오름차순·내림차순 구간을 탐지하고 짧은 구간은 이진 삽입 정렬로 늘린다. run 길이의 불변 조건을 유지하며 병합하고, galloping 모드로 편향된 비교를 가속한다. 구현에서 각 단계의 선택이 최종 결과의 올바른 순서·위치를 유지하는지 확인해야 한다. 반복 또는 재귀의 경계와 동일한 키를 가진 원소의 처리 역시 실행 결과에 영향을 준다.
시간·메모리 성질은 최악 O(n log n), 이미 정렬된 데이터는 O(n)에 가까움 적용하려면 안정적인 비교 연산과 run의 병합 버퍼가 필요하다 따라서 계산 복잡도는 원소 수뿐 아니라 입력의 정렬 상태, 키 범위 또는 비교·이동 비용처럼 알고리즘이 가정하는 자료 특성과 함께 분석해야 한다.
Python·Java 등의 객체·배열 정렬 구현에 영향을 주었다. 메모리 사용은 run 스택과 병합 버퍼 구현에 따라 달라진다. 동일한 목적의 다른 알고리즘과 비교할 때에는 안정성, 원소 이동의 양, 캐시 접근 패턴, 전처리 필요성과 최악 입력에서의 시간 비용을 함께 검토한다. 구체적인 계산 모델은 대상 자료구조 및 구현에 따라 달라진다.[2]