정렬 알고리즘

sorting algorithm, 정렬 알고리즘, sort, sorting, 정렬

정의

정렬 (sort) 은 원소들의 컬렉션을 어떤 전순서 (total order) 기준으로 재배열하는 것. 알고리즘 입문의 정석 주제이자, 데이터베이스·검색·통계 등 모든 시스템의 기반.

같은 결과 (정렬된 배열) 를 만드는 방법은 수십 가지가 있고, 데이터 크기·메모리·중복 처리·하드웨어 에 따라 최적의 선택이 달라진다.

자세한 메모리 비용 (정렬이 메모리를 다 쓰면 어떻게 디스크로 흘러가는지) 은 정렬·해시는 메모리가 부족하면 어디로 새는가, PGA, work_mem, Workspace Memory 글 참고.

핵심 분류

비교 정렬 vs 분포 정렬

구분	설명	예
비교 (comparison)	두 원소를 비교 (<, >) 해서 순서 결정. 최소 O(n log n) 하한 (정보이론적 하한)	Merge, Quick, Heap, Bubble, Insertion, Selection
분포 (distribution)	원소 값을 키로 직접 배치. O(n) 가능하지만 키 범위 제약	Counting Sort, Radix Sort, Bucket Sort

이 위키에서는 주로 비교 정렬 을 다룬다.

In-place vs Out-of-place

• In-place: 입력 배열 자체를 재배열. O(1) ~ O(log n) 추가 메모리
• Out-of-place: 별도 메모리 필요. 일반적으로 O(n)

Stable vs Unstable

• Stable: 같은 키를 가진 원소들의 원래 순서 가 보존됨
• Unstable: 같은 키 원소들의 순서가 뒤바뀔 수 있음

같은 키가 여러 번 등장하고 그 부속 정보가 중요할 때 (예: “성으로 정렬한 뒤 이름으로 정렬” → 안정 정렬이어야 성-이름 모두 정렬됨) 안정성이 중요하다.

비교 정렬 한눈에

알고리즘	최선	평균	최악	공간	안정	비고
Bubble Sort	O(n)	O(n²)	O(n²)	O(1)	✓	교육용. 거의 정렬된 입력에 빠름
Insertion Sort	O(n)	O(n²)	O(n²)	O(1)	✓	작은 n / 거의 정렬된 입력. 표준 라이브러리에서 작은 부분에 사용
Selection Sort	O(n²)	O(n²)	O(n²)	O(1)	✗	비교 횟수는 많지만 교환은 최소 (n번)
Merge Sort	O(n log n)	O(n log n)	O(n log n)	O(n)	✓	항상 일정. 외부 정렬의 기반
Quick Sort	O(n log n)	O(n log n)	O(n²)	O(log n)	✗	평균 빠름. 대부분의 표준 라이브러리
Heap Sort	O(n log n)	O(n log n)	O(n log n)	O(1)	✗	in-place + 일정. Top-K 문제에 유용

외부 정렬

데이터가 메모리에 들어가지 않을 때 사용. RDBMS 가 ORDER BY, GROUP BY, DISTINCT 같은 연산을 처리할 때의 주력 알고리즘.

• External Merge Sort, Run 생성 + K-way Merge

선택 가이드

상황	추천
n ≤ 20	Insertion Sort (작은 상수항)
일반 메모리 내 정렬	Quick Sort (또는 Introsort = Quick + Heap fallback)
안정성이 필요	Merge Sort (또는 Timsort, Java/Python 의 표준)
입력이 거의 정렬됨	Insertion Sort 또는 Timsort
데이터 > 메모리	External Merge Sort
메모리 매우 제한 (in-place + 일정)	Heap Sort
Top-K 만 필요	Heap (전체 정렬 X, 부분 정렬)
키 범위가 작은 정수	Counting Sort (O(n + k))

표준 라이브러리에서 무엇을 쓰는가

언어	알고리즘	안정
C qsort	Quicksort 변형	✗
C++ std::sort	Introsort (Quick + Heap fallback)	✗
C++ std::stable_sort	Merge Sort (또는 변형)	✓
Java Arrays.sort (객체)	Timsort	✓
Java Arrays.sort (원시 타입)	Dual-Pivot Quicksort	✗
Python list.sort() / sorted()	Timsort	✓
Rust slice::sort	Timsort 기반	✓
Rust slice::sort_unstable	Pdqsort (Pattern-defeating Quicksort)	✗
JavaScript Array.prototype.sort	ES2019 부터 stable 의무 (구현은 엔진별, V8 은 Timsort)	✓

Timsort 가 안정 정렬의 사실상 표준. Merge + Insertion 의 하이브리드로, 실제 데이터에서 자주 나타나는 “부분적으로 정렬된” 패턴 (run) 을 활용한다.

RDBMS 와의 관계

DB 가 ORDER BY 를 처리할 때:

데이터 크기	알고리즘	I/O
메모리 ≥ 데이터	Quicksort 또는 Heapsort (LIMIT N)	0
메모리 < 데이터 ≤ √(D·P)² 메모리	External Merge Sort, 1 패스	2 × 데이터
메모리 매우 부족	External Merge Sort, 다중 패스	K × 2 × 데이터

자세한 메커니즘은 정렬·해시는 메모리가 부족하면 어디로 새는가, PGA, work_mem, Workspace Memory 참고.

참고

• Merge Sort
• Quick Sort
• Heap Sort
• Bubble Sort
• Insertion Sort
• Selection Sort
• External Merge Sort
• 정렬·해시는 메모리가 부족하면 어디로 새는가, PGA, work_mem, Workspace Memory
• Knuth, The Art of Computer Programming, Vol. 3: Sorting and Searching