정렬 알고리즘: 삽입·병합·3-way 퀵 정렬의 불변식과 Java 선택 기준

정렬은 “숫자를 작은 순서로 놓는다”보다 큰 계약이다. 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 프로그램이다.

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");
    }
}

javac --release 21 SortingDemo.java
java SortingDemo

직접 실행한 출력은 다음과 같다.

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
Robert Sedgewick, Kevin Wayne, Algorithms, 4th Edition — Mergesort
Robert Sedgewick, Kevin Wayne, Algorithms, 4th Edition — Quicksort
Oracle, Arrays.sort — Java SE 21 API
Oracle, Comparator — Java SE 21 API
C. A. R. Hoare, Quicksort, The Computer Journal 5(1), 1962
Oracle, The Java Virtual Machine Specification, Java SE 21 — JVM Stacks and Heap