12강. 병합 정렬과 분할 정복: 큰 문제를 나누어 정렬하기

?1. 이번 강의에서 해결할 문제

O(n²) 정렬은 입력이 커질수록 비교 수가 급격히 늘어납니다. 문제를 균형 있게 나누고 결과를 합치는 전략이 필요합니다.

✓2. 학습 목표

✓이 강의를 마치면

• 분할·정복·결합 단계를 설명합니다.
• 병합 정렬의 재귀 종료 조건과 병합을 구현합니다.
• O(n log n) 시간과 O(n) 보조 공간을 분석합니다.

◇3. 핵심 개념

분할 정복은 문제를 작은 같은 형태의 문제로 나누고, 각각 해결한 뒤 결합합니다. 병합 정렬은 길이 0 또는 1이면 이미 정렬된 것으로 보고, 중간을 기준으로 두 구간을 정렬한 다음 작은 값부터 임시 배열에 병합합니다. 깊이는 O(log n), 각 깊이 전체 병합 비용은 O(n)이라 모든 상황에서 O(n log n)입니다.

✎4. 단계별 실습

1. 예제 파일 작성

실행 환경: 코드 편집기

실행 위치: C:\dev\game-ranking-algorithms

실행 전 확인: 같은 이름의 파일이 있다면 덮어쓰기 전에 Git diff로 변경 범위를 확인합니다. 선택한 LTS JDK의 java -version과 javac -version이 모두 실행되어야 합니다.

대상 파일: src/MergeSortDemo.java

src/MergeSortDemo.java

import java.util.Arrays;

public class MergeSortDemo {
    static void sort(int[] values) { sort(values, new int[values.length], 0, values.length); }
    static void sort(int[] a, int[] temp, int from, int to) {
        if (to - from <= 1) return;
        int mid = from + (to - from) / 2;
        sort(a, temp, from, mid);
        sort(a, temp, mid, to);
        int i = from, j = mid, k = from;
        while (i < mid && j < to) temp[k++] = a[i] <= a[j] ? a[i++] : a[j++];
        while (i < mid) temp[k++] = a[i++];
        while (j < to) temp[k++] = a[j++];
        for (k = from; k < to; k++) a[k] = temp[k];
    }

    public static void main(String[] args) {
        int[] scores = {1300, 700, 1500, 900, 900};
        sort(scores);
        System.out.println(Arrays.toString(scores));
    }
}

2. PowerShell에서 컴파일·실행

실행 환경: Windows PowerShell

실행 위치: C:\dev\game-ranking-algorithms

실행 전 확인: src/MergeSortDemo.java가 저장되었고 out 폴더에는 삭제해도 되는 컴파일 결과만 있는지 확인합니다.

대상: src/MergeSortDemo.java와 out 아래 생성되는 class 파일

Windows PowerShell

Set-Location C:\dev\game-ranking-algorithms
New-Item -ItemType Directory -Force .\out | Out-Null
javac -Xlint:all -d .\out .\src\MergeSortDemo.java
java -cp .\out MergeSortDemo

예상 결과: [700, 900, 900, 1300, 1500]이 출력됩니다.

실행 시간은 PC의 CPU·메모리, JDK 버전, JVM 워밍업, 백그라운드 작업과 입력 분포에 따라 달라질 수 있습니다. 측정값은 같은 조건에서 여러 번 비교하고 Big-O 분석과 함께 해석합니다.

→5. 코드와 알고리즘이 동작하는 이유

각 재귀 호출은 반 열린 구간 [from, to)를 다뤄 경계를 일관되게 합니다. <=일 때 왼쪽 값을 먼저 선택하면 같은 키의 상대 순서를 유지하는 안정 정렬이 됩니다. 보조 배열은 O(n), 재귀 스택은 O(log n)이며 전체 시간은 최선·평균·최악 O(n log n)입니다.

!6. 자주 하는 실수와 해결법

!자주 하는 실수

• 실수: 종료 조건 없이 길이 1도 다시 나누기 해결: 구간 길이가 1 이하면 반환합니다.
• 실수: 병합 뒤 원본 배열로 복사하지 않기 해결: 정렬 결과가 다음 상위 병합에 보이도록 복사합니다.
• 실수: O(n log n)이라 추가 공간도 작다고 가정하기 해결: 보조 배열 O(n)을 별도로 기록합니다.

✎7. 직접 실습

✎직접 실습

1. 정렬 전후 원소 개수와 합이 같은지 검사합니다.
2. 내림차순 병합으로 바꿉니다.
3. 길이 0, 1, 홀수, 중복 배열의 재귀 구간을 손으로 그립니다.

실습 기록에는 입력 크기, 예상 결과, 실제 결과, 시간·공간 복잡도와 사용한 JDK 버전을 함께 남깁니다. 실제 사용자 ID나 개인정보 대신 P1, P2 같은 가상 데이터를 사용합니다.

?8. 이해 점검 질문 3개

?이해 점검

1. 병합 정렬의 세 단계는 무엇인가요?
2. 각 재귀 깊이의 전체 병합 비용이 O(n)인 이유는 무엇인가요?
3. 안정성을 유지하는 비교 조건은 무엇인가요?

■9. 핵심 요약

■핵심 요약

병합 정렬은 균형 분할과 선형 병합으로 모든 상황 O(n log n)을 달성합니다. 대신 O(n) 보조 공간과 정확한 구간 경계 관리가 필요합니다.