정렬 계약
정렬은 원소를 어떤 순서로 다시 배치하는 연산입니다. 구현을 고르기 전에 입력 원소, 비교 기준, 결과의 사용처를 문장으로 고정해야 합니다. 예를 들어 주문을 금액 오름차순으로 보여 주되 금액이 같은 주문은 접수 순서를 유지한다면, 출력은 단순한 비감소 순서가 아니라 안정 정렬까지 요구합니다.
비교 기준은 두 원소의 앞뒤를 결정하는 규칙입니다. 같은 점수인 두 레코드를 동점으로 볼지, 이름과 입력 순번을 보조 기준으로 넣을지는 이 규칙의 일부입니다. 비교가 서로 모순되거나 NaN·대소문자·지역별 정렬 규칙을 일관되게 처리하지 않으면 알고리즘의 전제가 깨집니다.
정렬된다는 말은 결과에서 앞 원소가 뒤 원소보다 크지 않다는 뜻입니다. 그러나 인접한 순서만 맞는다고 입력 원소가 모두 남았다는 보장은 없습니다. 구현은 순서뿐 아니라 입력 다중집합, 즉 각 원소의 개수와 레코드 정체성도 보존해야 합니다.
안정성은 같은 비교 키를 가진 레코드의 입력 순서를 보존하는 속성입니다. 제자리 정렬은 정렬 배열 밖에서 쓰는 추가 공간의 범위에 대한 속성이고, 최악 시간은 모든 입력에서 지켜지는 상한입니다. 세 속성은 서로 다른 질문이므로 한 가지를 확인했다고 다른 둘을 추론하지 않습니다.
기본 정렬의 상태
삽입 정렬은 이미 정렬된 왼쪽 구간에 다음 원소를 알맞은 위치로 끼워 넣습니다. 현재 원소보다 큰 값만 오른쪽으로 밀면 같은 키의 앞뒤가 유지됩니다. 입력이 거의 정렬됐거나 원소 수가 작을 때는 이동량이 작고 구현의 상태가 단순하다는 장점이 있습니다.
선택 정렬은 남은 구간에서 최솟값의 위치를 기억한 뒤 한 번 교환합니다. 비교 횟수는 입력의 정렬 상태와 크게 무관하지만, 원소 이동 횟수를 줄일 수 있습니다. 일반적인 교환은 동점 레코드의 위치를 바꿀 수 있으므로 안정성이 필요하면 별도 구현 계약이 필요합니다.
버블 정렬은 인접한 역순 쌍을 교환하며 큰 값을 뒤로 보냅니다. 같은 값은 교환하지 않고 한 번의 순회에서 교환이 없으면 종료하도록 만들면 안정성과 이미 정렬된 입력의 조기 종료를 얻을 수 있습니다. 그래도 큰 역순 입력에서는 비교와 이동이 많으므로 교육용 추적 외의 기본 선택으로 삼을 근거는 workload에 두어야 합니다.
작은 입력 [5, 1, 4, 2]를 오름차순으로 정렬하면 세 알고리즘의 차이가 드러납니다.
| 단계 | 삽입 정렬의 정렬 구간 | 선택 정렬의 확정 구간 | 버블 정렬의 결과 |
|---|---|---|---|
| 시작 | [5] |
[] |
[5,1,4,2] |
| 1 | [1,5] |
최솟값 1을 0번에 교환 | [1,4,2,5] |
| 2 | [1,4,5] |
남은 최솟값 2를 1번에 교환 | [1,2,4,5] |
| 3 | [1,2,4,5] |
남은 구간은 이미 확정 | [1,2,4,5] |
표의 배열은 각 알고리즘이 같은 시점에 같은 상태를 가진다는 뜻이 아니라, 무엇을 불변식으로 확정하는지 비교하기 위한 trace입니다. 삽입 정렬은 왼쪽 구간 전체가 정렬되어 있고, 선택 정렬은 앞쪽 위치가 최종값이며, 버블 정렬은 한 순회 뒤 가장 큰 값이 뒤로 이동합니다.
비교 정렬의 비용
| 알고리즘 | 시간 상한의 핵심 | 추가 공간 | 안정성의 일반 구현 |
|---|---|---|---|
| 삽입 정렬 | 최악 O(n²), 거의 정렬된 입력에서 이동량 감소 | O(1) | 가능 |
| 선택 정렬 | O(n²) | O(1) | 보통 불안정 |
| 버블 정렬 | O(n²) | O(1) | 가능 |
| 병합 정렬 | O(n log n) | 보통 O(n) | 가능 |
| 퀵소트 | 평균 O(n log n), 최악 O(n²) 가능 | 재귀 스택 등 | 보통 불안정 |
| 힙 정렬 | O(n log n) | O(1) 수준 구현 가능 | 보통 불안정 |
표의 비용은 비교와 원소 이동을 추상화한 것입니다. 긴 문자열을 비교하거나 레코드가 크면 비교 횟수보다 비교 바이트와 복사 바이트가 지배할 수 있습니다. 실제 선택에서는 메모리 대역폭, 캐시, 할당, 입력 분포와 결과 계약을 같은 조건에서 분리해 봅니다.
병합과 퀵소트의 분할
병합 정렬은 입력을 두 구간으로 나누어 각각 정렬한 다음, 두 구간의 앞 원소를 비교해 작은 쪽을 출력합니다. 두 구간이 이미 정렬되어 있으면 전체에서 다음으로 출력할 원소는 반드시 두 앞 원소 중 하나입니다. 두 값이 같을 때 왼쪽 구간을 먼저 꺼내면 안정성이 유지됩니다.
퀵소트는 피벗을 기준으로 작은 구간과 큰 구간을 나누고 두 구간을 다시 정렬합니다. Lomuto 분할을 사용한다면 검사된 구간의 앞쪽에는 피벗 이하, 그다음에는 피벗보다 큰 원소를 둡니다. 분할 뒤 피벗 위치는 확정되므로 재귀 호출에서 제외해야 종료가 보장됩니다.
[4, 2, 5, 1, 3]에 마지막 원소 3을 피벗으로 적용하면 한 번의 분할 뒤 [2, 1, 3, 4, 5]가 됩니다. 3은 제자리에 있지만 왼쪽 [2,1]과 오른쪽 [4,5]는 아직 정렬되지 않았습니다. 매 호출에서 피벗을 제외한 구간이 실제로 줄어드는지 확인하지 않으면 같은 구간을 다시 처리하는 오류가 생깁니다.
정렬된 입력에서 매번 끝값을 피벗으로 택하면 한쪽 구간의 길이가 계속 n-1이 되어 O(n²)이 됩니다. 무작위 피벗은 나쁜 분할의 입력 상관을 약화할 수 있지만 최악 상한을 없애지는 않습니다. 최악 시간 상한이 필요하면 깊이 예산 소진 시 힙 정렬로 전환하는 introsort 같은 라이브러리 계약을 확인합니다.
키 기반 정렬
키의 값 범위가 작다면 비교 대신 키를 배열 위치로 사용할 수 있습니다. 계수 정렬은 0부터 100까지의 정수처럼 범위 R이 작을 때 각 값의 개수를 세고 순서대로 출력합니다. 시간은 O(n+R)로 분석하지만, 범위가 수십억이고 원소가 백 개뿐이면 카운터 배열이 데이터보다 큰 비용이 됩니다. 음수 범위는 기준점을 옮기거나 키 변환을 명시해야 합니다.
기수 정렬은 키를 여러 자리로 나누어 분배를 반복합니다. 낮은 자리부터 처리하는 LSD 방식은 각 자리의 분배가 안정적이어야 앞 단계의 동점 순서가 다음 단계에서도 남습니다. 가변 길이 문자열에서는 종료 기호, 바이트 순서, 유니코드 정규화와 언어별 정렬 규칙을 먼저 정해야 하며, “문자열에는 적용할 수 없다”라고 일반화하지 않습니다.
고정 폭 2의 보수 signed 정수는 부호 비트를 뒤집은 키를 unsigned 순서로 비교하는 변환을 사용할 수 있지만, 언어의 overflow와 비트 연산 규칙을 확인해야 합니다. 이 변환을 부동소수점이나 임의 길이 정수에 그대로 적용하지 않습니다. 결과에 원본 순서가 필요하면 안정 분배 또는 (키, 원본 순번)을 비교하는 명시적 설계를 사용합니다.
외부 병합의 자원
전체 데이터가 메모리에 들어가지 않으면 외부 병합 정렬을 사용합니다. 메모리에 들어오는 묶음을 읽어 정렬한 임시 파일을 만들고, 각 파일이 이미 정렬되어 있다는 성질을 이용해 병합합니다. 이를 정렬된 연속 입력 묶음인 run이라고 부릅니다.
예산이 3개 원소인 입력 [7,2,5,1,8,3,6,4]는 R0=[2,5,7], R1=[1,3,8], R2=[4,6]으로 나뉩니다. 처음 후보는 2, 1, 4이고 1을 출력한 뒤에는 R1에서만 3을 읽습니다. run이 k개면 최소 힙의 후보는 최대 k개이고 병합 비교 비용은 O(N log k)입니다.
fan-in은 한 번에 병합하는 run 수입니다. 100개 run을 10개씩 합치면 100→10→1의 두 단계가 필요하지만, 입력 버퍼·출력 버퍼·힙·디코딩 객체와 열린 파일 수가 늘어납니다. 메모리 예산에는 k*입력 버퍼 + 출력 버퍼 + 힙과 디코딩 + 실행 여유를 함께 넣고, 단계가 만드는 추가 디스크 읽기·쓰기도 계산합니다.
중단된 출력은 최종 파일 이름으로 공개하지 않습니다. 임시 이름, 정렬 기준 버전, 레코드 수, 체크섬과 완료 상태를 기록하고 검증 뒤 원자적 이름 교체를 수행합니다. 이름 교체만으로 전원 손실 뒤의 내구성이 보장되는 것은 아니므로 파일·디렉터리 flush 계약과 재개 정책을 별도로 확인합니다.
그림을 글로 읽기
- 레코드·키·입력 분포: 중복 점수와 거의 정렬된 구간
- 정렬 결과 계약: 순서·다중집합·동점 순서
- 알고리즘 후보: 삽입·병합·퀵·힙·기수
- 속성·비용 검증
- 레코드·키·입력 분포 → 정렬 결과 계약: 요구 고정
- 정렬 결과 계약 → 알고리즘 후보: 조건 대입
- 알고리즘 후보 → 속성·비용 검증: 동일 입력 비교
선택과 운영
먼저 정렬 기준과 동점 의미를 작은 레코드 예로 고정합니다. 그다음 입력 크기, 변경 빈도, 메모리 상한, 키 범위, 이미 존재하는 정렬 run, 외부 파일 여부를 측정합니다. 마지막으로 안정성, 최악 시간, 재귀 깊이, 임시 저장소를 독립적인 수용 조건으로 만듭니다.
다음은 설명용 의사코드입니다. 특정 언어 표준 라이브러리의 내부 구현이 아니며 comparator가 일관된 전순서를 제공하고, key_encoding이 비교 대상의 의미를 보존한다는 전제를 둡니다.
sortRecords(records, contract):
require comparator_is_consistent(contract.comparator)
require multiset_and_tie_policy_is_defined(contract)
if not records_fit_in_memory:
return external_merge_sort(records, contract.memory_budget)
if contract.key_range_is_small and auxiliary_storage_fits_budget:
return stable_count_or_radix(records, contract.key_encoding)
if records.size is small or nearly_sorted(records):
return insertion_sort(records)
if contract.needs_stable_output:
return stable_merge_sort(records)
return introsort_or_library_sort(records)
검증에서는 빈 배열, 한 원소, 역순, 모두 같은 키, 중복 레코드, 긴 문자열, 범위를 벗어난 키와 디스크 부족을 사용합니다. 결과의 비감소 순서, 입력 다중집합 보존, 동점 원본 순서를 따로 검사합니다. 비교 횟수, 이동 바이트, 최대 재귀 깊이, 메모리 피크와 임시 디스크 사용량도 기록합니다.
운영 중에는 평균 지연 하나로 선택을 고정하지 않습니다. 입력 크기별 p95·p99, 중복률, 최악 패턴, 메모리 압박, 외부 정렬의 run 수와 병합 단계, 임시 파일 잔존량을 함께 관찰합니다. 정렬 결과가 캐시 키나 페이지 diff의 입력이면 동점 순서 변화도 오류 신호로 취급합니다.
참고 자료와 검증 범위
- 감사 대상 Algorithm README — 2026-09-17 확인, 커밋
26c959a31f279295931130833cb6d0a43592e26e, 비교·비교 불가 정렬과 설계 전략의 원문 범위입니다. - 정렬 안정성과 introsort의 서로 다른 보장 — 기존 심화 노트, 안정성·최악 시간·스택 상한의 연결 자료입니다.
- 퀵소트의 분할과 최악 시간 — 기존 심화 노트, 분할 불변식과 퇴화 입력의 연결 자료입니다.
- 계수 정렬과 기수 정렬의 키 표현 — 기존 심화 노트, 안정 분배·signed 키·가변 문자열의 연결 자료입니다.
- 외부 병합 정렬의 버퍼와 복구 경계 — 기존 심화 노트, run·fan-in·완료 파일 공개의 연결 자료입니다.
이 장의 표와 trace는 논리 예이며 이 문서의 작성 과정에서 성능 벤치마크나 특정 표준 라이브러리의 내부 구현을 실행해 확인한 결과가 아닙니다. 실제 선택 전에는 목표 언어·라이브러리와 workload에서 속성 및 비용을 측정해야 합니다.