Python에서 “정렬된다”는 말에는 안정성, 비교 방향, key 계산 시점, 입력 순서라는 서로 다른 계약이 들어 있습니다. 안정 정렬은 동점자의 현재 입력 순서를 보존할 뿐 전역 결정성을 만들어 주지 않으므로, 원하는 출력 계약을 먼저 정한 뒤 자료구조와 보조 키를 선택해야 합니다.
안정 정렬과 동점자의 입력 순서 보존
점수가 같은 A와 B를 [A, B] 순서로 넣으면 안정 정렬은 두 원소를 동점으로 보고 그 순서를 그대로 둡니다. [B, A]를 넣으면 결과도 [B, A]이므로, 안정 정렬이 보장하는 것은 동점자의 입력 순서 보존이지 입력 순서와 무관한 결과가 아닙니다. 여러 worker 결과처럼 합치는 순서가 달라질 수 있는 자료에서 항상 같은 랭킹을 원한다면 점수 뒤에 최종 ID 같은 보조 키를 실제 비교에 넣어야 합니다.
Python의 list.sort와 sorted는 안정 정렬을 제공합니다. list.sort는 원본을 바꾸고 None을 반환하며 sorted는 새 리스트를 만듭니다. 원본 순서를 보존해야 할 때 sort를 쓴 뒤 안정적이므로 안전하다고 말할 수는 없습니다.
연속 안정 정렬과 마지막 키의 우선순위
rows = [('A', 10, 2), ('B', 10, 1), ('C', 20, 3)]
rows.sort(key=lambda r: r[2]) # 가입 순서
rows.sort(key=lambda r: r[1], reverse=True) # 점수 우선
print([r[0] for r in rows]) # ['C', 'B', 'A']
두 번째 안정 정렬은 점수가 같은 항목 사이에서 첫 번째 정렬이 만든 가입 순서를 보존하므로, 이 코드에서는 먼저 가입 순서가 B, A, C가 되고 점수 내림차순 정렬 뒤 C, B, A가 됩니다. 복합 키 (-score, joined, id)를 쓰면 같은 우선순위를 한 번에 표현할 수도 있지만, 각 값의 타입과 음수 변환이 안전한지, 오름·내림 방향을 어떻게 섞을지 먼저 정해야 합니다.
모든 구성요소를 같은 방향으로 정렬하려는 것이 아니라면 reverse=True 하나가 각 필드의 의도를 그대로 나타내는지도 확인해야 합니다.
| 요구 | 키·입력 정책 | 잘못된 대체 |
|---|---|---|
| 문서의 동점 입력 순서 보존 | stable sort | 임의 ID를 추가해 순서 변경 |
| 전역 결정적 랭킹 | 최종 유일 tie-breaker | stable만 의존 |
| 원본 목록 유지 | sorted 또는 명시 복사 | list.sort 반환값 사용 |
| 혼합 타입·NaN | 정규화·거절·별도 순서 | 모든 값이 자연 비교 가능하다고 가정 |
정렬 run 활용과 구현 시간 최적화
CPython의 정렬은 입력 안에서 이미 정렬된 연속 구간인 run을 찾아 준비한 뒤, 그 구간들을 병합하는 적응형 정렬 계열입니다. 부분 정렬되었거나 정렬이 끝난 입력에서는 기존 run을 활용해 비교와 이동을 줄일 수 있지만, 모든 입력의 시간이 선형이 되는 것은 아닙니다. 따라서 Timsort라는 이름만으로 버전별 병합 정책·run 처리·버퍼 크기까지 영구 계약이라고 단정하지 않습니다.
그림을 글로 읽기
- 부분 정렬 입력
- 연속 run 탐지·준비
- run들을 안정적으로 병합
- 전체 순서·동점 안정성
- 부분 정렬 입력 → 연속 run 탐지·준비: 입력 구조 활용
- 연속 run 탐지·준비 → run들을 안정적으로 병합: 구현의 병합 정책
- run들을 안정적으로 병합 → 전체 순서·동점 안정성: 정렬 결과
최악 비교 비용과 임시 메모리를 함께 고려합니다. 비교 중 원본 리스트를 수정하거나 일관되지 않은 비교를 제공하는 것은 안전한 일반 정렬 계약이 아닙니다. 변경 중 데이터는 snapshot으로 고정하고 키 함수의 부수 효과를 줄입니다.
Key 함수의 원소별 평가와 값 재사용
key 기반 정렬은 n개 원소의 key를 먼저 한 번씩 계산한 뒤, 정렬 과정에서는 그 값을 재사용합니다. 따라서 n=1000에서 key 호출 횟수는 정상 경로에서 정렬 비교 횟수가 아니라 1000으로 계측되어야 하며, key가 예외를 던져 중단되는 경우는 별도 경로입니다. 매 비교마다 외부 조회·복잡한 계산을 하는 comparator와 비용 구조가 다른 이유가 여기에 있습니다.
여러 번 정렬하면서 같은 비싼 key를 재사용하려면 별도 사전 계산·캐시의 신선도·메모리 정책이 필요합니다. key가 현재 시각·외부 DB·가변 상태를 읽으면 원소별 평가 시점이 달라져 재현성이 흔들릴 수 있습니다. 키 계산·비교·목록 생성·병합 비용을 따로 측정하고 같은 결과를 비교합니다.
Set 순서·Runtime Hash와 외부 결정성 계약
set의 순회는 안정적인 정렬 순서 보장이 아닙니다. 문자열 등의 hash randomization과 내부 배치가 실행 간 순서에 영향을 줄 수 있습니다. dict의 삽입 순서 보장은 입력을 set에서 얻어 삽입하는 순서 자체까지 결정적으로 만들지 않습니다.
서명 입력·캐시 샤딩·영구 ID에 프로세스의 hash 결과를 그대로 쓰지 않습니다. 필요하면 명시적인 바이트 인코딩·정규화·안정 해시 알고리즘·버전을 고정합니다. 재현을 위해 테스트 seed를 고정할 수는 있어도 외부 출력 순서의 버그를 감추려고 보안 무작위화를 영구 제거하는 것은 다른 선택입니다.
작은 입력 [A, B]와 [B, A]를 같은 점수로 정렬하고, sorted와 list.sort의 원본·반환값을 각각 관찰하십시오. 예상 결과는 동점 순서가 입력을 따라가고 list.sort의 반환값은 None이며, 최종 ID를 보조 키로 넣었을 때만 입력 조립 순서가 달라도 같은 랭킹이 된다는 것입니다. set에서 시작한 출력은 별도 프로세스와 여러 PYTHONHASHSEED에서 다시 확인합니다.
입력 분포·PYTHONHASHSEED 변화와 정렬·출력 결정성 시험
동점 입력 순서 두 가지, sorted 원본 보존, key 호출 수, 부분 정렬·역순·무작위 입력을 시험합니다. set 기반 출력은 여러 PYTHONHASHSEED의 새 프로세스로 실행하고 순서가 계약이면 최종 정렬이 같은지 확인합니다. 원소 집합만 요구하는 테스트는 집합으로 비교합니다.
키의 성능 비교는 Python 구현·버전·원소 수·run 비율·키 비용·할당을 고정합니다. 이 노트는 의미와 측정 설계이며 특정 최신 CPython 정렬 구현의 성능을 실제 측정한 결과는 아닙니다.