--- title: "정렬 알고리즘: 삽입·병합·3-way 퀵 정렬의 불변식과 Java 선택 기준" slug: "java-sorting-algorithms" category: "CS" topic: "cs" subtopic: "algorithms" tags: ["Java","Sorting","Insertion Sort","Merge Sort","Quicksort"] status: "published" created: "2026-08-06" updated: "2026-08-06" summary: "삽입·병합·3-way 퀵 정렬을 같은 입력 계약으로 실행하고, 안정성·최악 시간·보조 배열·재귀 frame·Java Arrays.sort 계약을 근거로 선택한다." kind: "Deep Dive" evidence: "Princeton Algorithms 4/e 정렬 절과 Java SE 21 Arrays API를 대조하고 세 구현을 역정렬·중복·빈 입력에서 OpenJDK 21.0.11로 교차 검증" series: "Java Essential Algorithms" --- 정렬은 “숫자를 작은 순서로 놓는다”보다 큰 계약이다. stable 여부, 원본 변경, comparator 일관성, 최악 latency, 보조 메모리까지 호출자에게 영향을 준다. 이 글은 삽입·병합·3-way quick sort를 같은 `int[]` 오름차순 계약으로 구현해 차이를 드러낸다. ## 1. 공통 계약과 안정성 세 method는 null이 아닌 `int[]`를 제자리 오름차순으로 만든다. 빈 배열, 한 원소, 중복, 음수를 허용한다. primitive 값만으로는 같은 key의 원래 순서를 관찰할 수 없으므로 안정성은 별도 record 예제로 정의해야 한다. stable sort는 비교 결과가 같은 객체의 상대 순서를 보존한다. Oracle `Arrays.sort` 문서는 primitive overload와 object overload의 계약/구현 note가 다르다. API 문서의 implementation note는 specification 자체와 구분해야 하며, 직접 구현보다 표준 library를 기본 선택으로 둔다. ## 2. 삽입 정렬: `[0,i)`가 이미 정렬돼 있다 현재 `a[i]`를 꺼내 정렬된 prefix에서 큰 원소를 오른쪽으로 밀고 빈자리에 넣는다. **불변식:** 바깥 loop 시작 시 `[0,i)`는 원래 그 구간 원소들의 정렬된 permutation이다. 더 큰 값만 이동한 뒤 current value를 넣으면 `[0,i+1)`도 정렬과 원소 보존을 만족한다. `>`일 때만 이동하면 같은 key를 넘어가지 않아 안정성을 보존할 수 있다. 이미 정렬된 입력은 각 i에서 비교 한 번 수준이라 $\Theta(n)$, 역정렬은 이동 횟수가 $1+2+...+(n-1)=n(n-1)/2$라 $\Theta(n^2)$이다. 추가 배열은 없다. ## 3. 병합 정렬: 정렬된 두 절반을 잃지 않고 합친다 `[lo,mid)`, `[mid,hi)`를 재귀적으로 정렬하고 작은 head부터 aux에서 원본으로 쓴다. **merge 불변식:** write index 이전에는 두 절반에서 소비한 원소 중 가장 작은 값들이 정렬되어 있고, left/right는 각 절반의 아직 쓰지 않은 최소 원소를 가리킨다. 둘 중 작은 값을 쓰면 다음 prefix도 최솟값 순서를 보존한다. 동률에 왼쪽을 먼저 쓰면 stable하다. level마다 총 $n$개를 병합하고 level이 $\lceil\log_2 n\rceil$개이므로 시간은 $\Theta(n\log n)$이다. aux `int[n]` 때문에 $O(n)$ heap 공간, 재귀 frame은 $O(\log n)$ 깊이다. ## 4. 3-way quick sort: `< pivot`, `== pivot`, `> pivot` partition 중 `[lo,lt)`는 pivot보다 작고, `[lt,scan)`은 같고, `[scan,gt]`는 미분류, `(gt,hi]`는 크다. scan 값을 보고 swap해 네 구간 불변식을 유지한다. 종료하면 같은 구간을 제외한 두 바깥만 재귀 정렬한다. 중복이 많을 때 equal block을 다시 정렬하지 않아 효율적이다. 하지만 예제처럼 첫 원소를 pivot으로 고르면 이미 정렬된 distinct 입력에서 partition이 심하게 치우쳐 $O(n^2)$ 시간과 $O(n)$ 재귀 깊이가 될 수 있다. production 구현은 randomization, better pivot, recursion depth 방어가 필요하다. ## 실행 재현 아래 코드는 설명용 조각이 아니라 `main`에 정상·빈 입력·중복·경계·실패 계약을 함께 넣은 완전한 Java 21 프로그램이다. ```java import java.util.Arrays; public final class SortingDemo { static void insertionSort(int[] a) { requireArray(a); for (int i = 1; i < a.length; i++) { int value = a[i]; int j = i - 1; while (j >= 0 && a[j] > value) { a[j + 1] = a[j]; j--; } a[j + 1] = value; } } static void mergeSort(int[] a) { requireArray(a); int[] aux = new int[a.length]; mergeSort(a, aux, 0, a.length); } static void mergeSort(int[] a, int[] aux, int lo, int hi) { if (hi - lo <= 1) return; int mid = lo + (hi - lo) / 2; mergeSort(a, aux, lo, mid); mergeSort(a, aux, mid, hi); if (a[mid - 1] <= a[mid]) return; System.arraycopy(a, lo, aux, lo, hi - lo); int left = lo; int right = mid; for (int write = lo; write < hi; write++) { if (left == mid) a[write] = aux[right++]; else if (right == hi) a[write] = aux[left++]; else if (aux[right] < aux[left]) a[write] = aux[right++]; else a[write] = aux[left++]; } } static void quickSort3Way(int[] a) { requireArray(a); quickSort3Way(a, 0, a.length - 1); } static void quickSort3Way(int[] a, int lo, int hi) { if (lo >= hi) return; int pivot = a[lo]; int lt = lo; int scan = lo + 1; int gt = hi; while (scan <= gt) { if (a[scan] < pivot) swap(a, lt++, scan++); else if (a[scan] > pivot) swap(a, scan, gt--); else scan++; } quickSort3Way(a, lo, lt - 1); quickSort3Way(a, gt + 1, hi); } static void requireArray(int[] a) { if (a == null) throw new IllegalArgumentException("array must not be null"); } static void swap(int[] a, int i, int j) { int temp = a[i]; a[i] = a[j]; a[j] = temp; } static void checkSort(int[] input) { int[] expected = input.clone(); Arrays.sort(expected); int[][] candidates = {input.clone(), input.clone(), input.clone()}; insertionSort(candidates[0]); mergeSort(candidates[1]); quickSort3Way(candidates[2]); for (int[] actual : candidates) { if (!Arrays.equals(expected, actual)) throw new AssertionError(Arrays.toString(actual)); } } public static void main(String[] args) { checkSort(new int[] {5, 1, 5, -2, 9, 0}); checkSort(new int[0]); checkSort(new int[] {1}); checkSort(new int[] {5, 4, 3, 2, 1}); checkSort(new int[] {7, 7, 7, 7}); System.out.println("insertion/merge/3-way-quick checks: OK"); } } ``` ```bash javac --release 21 SortingDemo.java java SortingDemo ``` 직접 실행한 출력은 다음과 같다. ```text insertion/merge/3-way-quick checks: OK ``` 컴파일러와 런타임은 `javac 21.0.11`, OpenJDK `21.0.11`을 사용했다. `assert` 옵션에 의존하지 않고 실패 시 `AssertionError`를 던지므로 위 명령 그대로 검증된다. ## 5. 실행 코드에서 확인할 세부사항 `mergeSort`는 이미 두 절반 경계가 정렬됐으면 merge copy를 생략한다. `quickSort3Way`는 duplicate `[7,7,7,7]`에서 equal 영역 한 번으로 끝난다. 모든 결과를 `Arrays.sort`의 결과와 교차 검증하지만 이것은 우리 구현의 완전한 수학 증명을 대체하지 않는다. 예제 quick sort는 교육용으로 최악 입력 방어가 없음을 의도적으로 드러낸다. 제목만 보고 production에 복사하면 안 된다. ## 6. 같은 기준으로 비교한다 | 알고리즘 | 최선 | 평균 | 최악 | 보조 공간 | stable | | --- | ---: | ---: | ---: | ---: | --- | | insertion | $O(n)$ | $O(n^2)$ | $O(n^2)$ | $O(1)$ | 구현 가능 | | merge | $O(n\log n)$ | $O(n\log n)$ | $O(n\log n)$ | $O(n)$ + frames | 예제는 yes | | 3-way quick | $O(n)$ all equal | 기대 $O(n\log n)$* | $O(n^2)$ | frames 평균 $O(\log n)$ | no | 별표의 기대값은 pivot 선택/입력 분포 가정이 필요하다. 첫 원소 pivot 예제에 무조건 적용하지 않는다. ## 7. JVM 메모리·boxing·comparator 입력 `int[]`와 merge aux는 heap array다. recursion마다 frame이 중첩되며 quick sort 최악 depth는 `StackOverflowError` 위험으로 이어진다. object array 정렬은 reference를 이동하고 comparator 호출을 반복한다. comparator가 boxing, allocation, I/O를 하면 비교 횟수뿐 아니라 그 비용이 지배한다. 정확한 byte보다 먼저 peak live set을 본다: merge는 input과 같은 길이 aux가 동시에 살아 있고, quick sort는 frame depth가 입력에 따라 달라진다. JFR로 allocation/stack trace, JMH로 분포별 throughput을 측정한다. ## 8. 실제 선택과 도메인 작고 거의 정렬된 run에는 insertion sort가 좋다. stable object ordering과 예측 가능한 최악 시간이 중요하고 $O(n)$ buffer가 허용되면 merge 계열이 맞다. primitive array의 일반 정렬은 직접 코드보다 `Arrays.sort`를 우선한다. 외부 정렬은 메모리에 다 못 올리는 파일을 sorted run으로 만들고 k-way merge하며 disk read/write와 spill을 비용 모델에 넣는다. Backend에서는 request마다 대량 정렬하지 말고 result size, comparator CPU, allocation, p99를 본다. DB `ORDER BY`는 index order, sort memory, disk spill을 execution plan으로 확인한다. Data pipeline은 partition skew와 merge fan-in을 본다. ## 9. 이건 피한다 - **교육용 quick sort를 production에 복사한다.** adversarial/정렬 입력에서 $O(n^2)$과 깊은 재귀가 난다. 표준 library나 depth 방어 구현을 쓴다. - **stable이 필요한 객체를 unstable sort한다.** 동률의 이전 순서가 깨져 pagination/UI가 흔들린다. stable 계약을 고른다. - **comparator 계약을 깨뜨린다.** 비추이적 비교는 결과 오류나 runtime exception을 낳는다. total order와 null 정책을 테스트한다. - **원본 변경 여부를 숨긴다.** in-place sort가 caller 상태를 바꾼다. copy 여부와 $O(n)$ 공간을 API에 드러낸다. - **Big-O 표만 보고 입력 분포를 무시한다.** 거의 정렬·중복·역정렬에서 경로가 다르다. 대표 분포를 JMH로 분리 측정한다. ## Reference - Robert Sedgewick, Kevin Wayne, [Algorithms, 4th Edition — Elementary Sorts](https://algs4.cs.princeton.edu/21elementary/) - Robert Sedgewick, Kevin Wayne, [Algorithms, 4th Edition — Mergesort](https://algs4.cs.princeton.edu/22mergesort/) - Robert Sedgewick, Kevin Wayne, [Algorithms, 4th Edition — Quicksort](https://algs4.cs.princeton.edu/23quicksort/) - Oracle, [Arrays.sort — Java SE 21 API](https://docs.oracle.com/en/java/javase/21/docs/api/java.base/java/util/Arrays.html) - Oracle, [Comparator — Java SE 21 API](https://docs.oracle.com/en/java/javase/21/docs/api/java.base/java/util/Comparator.html) - C. A. R. Hoare, [Quicksort, The Computer Journal 5(1), 1962](https://doi.org/10.1093/comjnl/5.1.10) - Oracle, [The Java Virtual Machine Specification, Java SE 21 — JVM Stacks and Heap](https://docs.oracle.com/javase/specs/jvms/se21/html/jvms-2.html#jvms-2.5)