정렬을 선택할 때 “정렬된다”는 한 문장으로는 부족합니다. 비교 키의 동점 의미, 안정성, 추가 공간, 최악 시간, 호출 스택을 별도 계약으로 적어야 같은 데이터에서 결과와 장애 양상을 예측할 수 있습니다.
동일 값 레코드의 순서 의미
입력이 (점수=80,이름=A), (90,B), (80,C)이고 점수로 정렬한다고 합시다.
상태를 직접 추적하면 차이가 분명합니다. 점수 정렬 전 원본 순번은 A=0, B=1, C=2이고, 안정 정렬 결과는 A, C, B입니다. 불안정 정렬은 80 그룹 내부를 C, A로 내놓아도 정렬 키 자체는 만족합니다. 같은 80 안에서 A가 C보다 먼저 남는 보장이 안정성이며, 키가 정렬됐다는 사실만으로 이 순서를 보장하지는 않습니다. 따라서 화면에서 동점 순서가 사용자 의미라면 안정 API를 확인하거나 (점수, 원본순번)을 비교 키로 명시해야 하며, 단순히 “빠른 정렬”을 고르는 것으로는 충분하지 않습니다.
여기서 ‘안정적’이라는 말은 오류가 적거나 실행 시간이 일정하다는 뜻이 아닙니다. 비교 결과가 같은 레코드의 앞뒤 관계를 보존한다는 좁고 구체적인 의미입니다.
‘제자리 정렬’은 다른 질문에 답합니다. 정렬할 배열 외에 얼마나 많은 저장 공간이 필요한지를 말합니다. 따라서 메모리를 적게 쓰면서 안정적일 수도 있고, 메모리를 더 쓰면서 불안정할 수도 있습니다.
삽입 정렬에서는 현재 값보다 큰 값만 오른쪽으로 밀면 같은 값의 순서가 유지됩니다. 별도 출력 배열 없이도 안정적으로 구현할 수 있는 예입니다. 반면 병합 정렬에서는 두 구간의 값이 같을 때 왼쪽 구간을 먼저 선택해야 원래 순서가 남습니다. 보조 배열을 사용한다는 사실만으로 안정성이 생기지는 않습니다.
비교자 기준과 동점 정의
두 레코드의 모든 필드가 같아야 동점인 것은 아닙니다. 비교자가 점수만 비교하면 이름이 달라도 같은 키입니다. 먼저 이름으로 안정 정렬하고 다음 점수로 안정 정렬하면 점수가 같은 그룹 안에서 이름 순서가 보존됩니다. 반면 두 번째 정렬이 불안정하면 첫 순서를 잃을 수 있습니다.
| 속성 | 질문 | 별도로 확인할 것 |
|---|---|---|
| 정렬됨 | 비교 기준대로 비감소하는가 | 비교자의 일관성 |
| 안정성 | 동점의 입력 순서가 남는가 | 원본 순번 |
| 제자리 | 추가 배열 없이 처리하는가 | 재귀 스택 포함 여부 |
| 최악 시간 | 어떤 입력에도 상한이 있는가 | 입력·비교 비용 전제 |
비교 키가 바뀌거나 NaN 처리·대소문자 규칙이 일관되지 않으면 알고리즘의 전제가 깨집니다. 안정성은 잘못된 비교자를 고쳐 주지 않습니다.
원본 순번을 보조 키로 만드는 대안
불안정 정렬만 있어도 (원래 키, 입력 순번)을 비교하면 동점 순서를 명시적인 전순서로 만들 수 있습니다. 그러나 순번 저장·비교 비용이 추가되고 기존 비교 의미가 확장됩니다. 모든 레코드의 입력 순번이 유일하고 범위를 넘지 않도록 해야 합니다.
그림을 글로 읽기
- 80:A · 90:B · 80:C: 원본 순번 0 · 1 · 2
- (80,0) · (90,1) · (80,2)
- 80:A · 80:C · 90:B
- 80:A · 90:B · 80:C → (80,0) · (90,1) · (80,2): 키·순번 결합
- (80,0) · (90,1) · (80,2) → 80:A · 80:C · 90:B: 사전식 비교
introsort의 퀵소트 최악 깊이 감시
퀵소트가 매번 0:n-1로 분할되면 깊이 O(n), 시간 O(n²)이 됩니다. Introsort는 일정 깊이 이상 내려가면 남은 구간을 heapsort로 처리하는 전략입니다. 예를 들어 처음 n에서 2 floor(log2 n) 같은 깊이 예산을 정할 수 있지만 정확한 상수와 작은 구간 처리 방식은 구현마다 다릅니다.
sortRange(range, depthBudget):
if range is small:
insertionSort(range)
return
if depthBudget == 0:
heapSort(range)
return
left,right = partitionExcludingFixedPivot(range)
sortRange(left, depthBudget-1)
sortRange(right, depthBudget-1)
깊이를 제한하면 왜 최악 시간이 달라질까요? 퀵소트의 분할 한 층에서는 서로 겹치지 않는 구간들을 처리합니다. 그 구간의 원소 수를 모두 합쳐도 n이므로, 한 층의 분할 작업은 O(n)입니다. 그런 층을 O(log n)까지만 허용하면 퀵소트 부분의 작업량은 O(n log n)을 넘지 않습니다.
그 시점에 남은 각 구간은 힙 정렬이 맡습니다. 크기 m인 구간의 비용은 O(m log m)이고, 남은 구간들은 서로 겹치지 않습니다. 따라서 이 비용을 모두 더해도 O(n log n) 안에 들어옵니다.
코드에서는 depthBudget-1을 자식에게 전달하는 부분이 중요합니다. 재귀 호출마다 같은 초기 예산을 다시 주면 제한이 소진되지 않아, 나쁜 분할이 계속되는 것을 막지 못합니다.
시간 상한과 스택 상한의 분리
깊이 제한이 있는 위 재귀는 O(log n) 깊이 안에서 heapsort로 전환합니다. 별도로 작은 쪽만 재귀 호출하고 큰 쪽은 반복문으로 처리하면 일반 퀵소트에서도 스택 깊이를 O(log n)으로 제한할 수 있습니다. 하지만 그 최적화만으로 분할의 O(n²) 시간은 없어지지 않습니다.
깊이 예산이 소진되어 heapsort로 바뀌는 순간은 최악 시간 상한을 위한 전환이지 동점 순서를 위한 전환이 아닙니다. 예를 들어 같은 점수의 A와 C가 partition 뒤 서로 다른 구간으로 이동하거나 heapsort에서 위치를 바꾸면 입력 순서가 달라질 수 있으므로, 흔한 introsort 전체를 안정적이라고 부를 수 없습니다. 작은 구간에서 삽입 정렬을 쓰더라도 다른 구간의 partition이나 heapsort가 안정성을 깨면 결론은 바뀌지 않으며, 실제 라이브러리 API가 안정성을 보장하는지는 별도로 확인해야 합니다. 비교 한 번이 긴 문자열·외부 호출에 비례한다면 O(n log n)은 비교 횟수에 대한 분석이고 실제 시간은 비교 비용까지 곱해 봐야 합니다.
서로 다른 속성의 개별 검사
키에 원본 순번을 붙인 중복 입력을 정렬해 값의 순서와 동점 순번을 따로 확인합니다. 정렬·역정렬·모두 같은 값·중복 집중 입력에서 비교 횟수와 최대 재귀 깊이를 측정합니다. 입력 다중집합 보존과 메모리 피크도 확인합니다.
성능 테스트에서 빠른 평균만 보고 최악 상한을 단정하지 않고, 안정성 테스트를 통과했다고 제자리라고 말하지 않습니다. 정렬 라이브러리를 선택할 때는 이 속성들이 각각 어떤 계약인지 명시해야 합니다.