Python에서 일부 정렬된 데이터를 다시 정렬하고 동점자의 기존 순서도 유지하려 합니다. sort의 보장과 이미 정렬된 구간을 활용하는 구현 특성을 어떻게 구분하나요?

Python의 list.sort()와 sorted()는 안정 정렬을 제공하며, 실제 CPython 구현은 입력에서 이미 정렬된 연속 구간인 run을 찾아 이를 활용하는 적응형 병합 정렬 계열입니다. 데이터가 부분적으로 정렬되어 있으면 무작위 입력보다 비교와 이동이 줄어들 수 있고, 완전히 정렬된 입력은 매우 유리한 경로를 탑니다. 그렇다고 모든 입력에서 선형 시간이 된다는 뜻은 아니며 일반적인 비교 정렬의 최악 시간과 추가 메모리 비용을 함께 봐야 합니다.

안정성이라는 결과 보장

안정성은 비교 키가 같은 원소의 입력 상대 순서를 보장한다는 언어 수준의 중요한 계약입니다. 그러나 안정성만으로 분산 환경의 결과가 재현되는 것은 아닙니다. 입력 순서 자체가 비결정적이면 동점 결과도 달라질 수 있으므로, 전역 순서가 필요하면 점수와 ID처럼 보조 키를 함께 비교하겠습니다.

run 최적화와 재현성

구현을 설명할 때는 “Python은 Timsort를 쓴다”에서 멈추지 않겠습니다. Python 언어·라이브러리 계약과 특정 구현(CPython)의 현재 알고리즘은 다른 층이며, CPython 버전별 소스의 run 탐지·병합 최적화나 임시 버퍼 세부를 애플리케이션 계약처럼 고정하면 업그레이드 때 깨질 수 있습니다. 성능을 이유로 정렬 입력 형태를 설계한다면 실제 Python 버전에서 대표 데이터로 측정하고, 결과 순서는 안정성·키 함수·비교 가능성으로 테스트하겠습니다.

선택 기준과 검증

안정성은 입력 상대 순서를 보존하는 결과 계약이고, run을 활용하는 것은 구현상의 시간 최적화입니다. 여러 워커에서 합친 입력 순서가 비결정적이면 안정 정렬만으로 결과가 재현되지 않으므로 ID 같은 최종 키를 추가하겠습니다. 키 함수 계산 비용과 비교 비용, 부분 정렬 비율을 분리해 Python 3.11+ 실제 입력으로 측정하겠습니다.

list.sort는 원본 리스트를 바꾸고 None을 반환하며 sorted는 새 리스트를 만듭니다. 원본 순서를 보존해야 하는 호출자에게 list.sort를 적용하면 알고리즘이 안정적이어도 API 계약이 깨집니다. key 함수는 원소마다 한 번 평가되므로 비교 때마다 비싼 계산을 하는 사용자 정의 비교보다 유리할 수 있지만, 여러 번의 정렬 사이에서 같은 키를 재사용하려는 요구는 별도 저장 정책이 필요합니다.

먼저 가입 시각으로 정렬한 뒤 점수로 안정 정렬하면 점수가 같은 그룹 안에서 가입 시각의 순서가 남습니다. 반대로 순서를 뒤집어 적용하면 우선순위도 바뀝니다. 복합 키 하나로 표현할 수도 있지만 내림차순·오름차순이 섞인 경우 각 구성 요소의 방향을 명시해야 합니다. 키 함수가 실행 중 값을 바꾸거나 비교 중 리스트를 수정하면 안전한 일반 계약이 아니므로, 정렬할 스냅샷과 순수한 키 함수를 사용하겠습니다.

예를 들어 점수가 같은 A와 B를 서로 다른 순서로 입력하면 안정 정렬은 각각의 입력 순서를 보존합니다. 두 결과가 다르다고 불안정한 알고리즘은 아닙니다. 결정적인 랭킹이 필요하면 점수 외의 최종 ID를 키로 포함하고, 원래 순서를 존중해야 하는 문서 목록에서는 임의의 ID 정렬로 그 의미를 바꾸지 않겠습니다.