이성주

현재를 즐기며 미래를 만드는 개발자, 이성주입니다.

Java에서 Arrays.sort() 또는 Collections.sort()를 사용할 때 내부적으로 어떤 정렬 알고리즘이 사용되는지, 그리고 왜 그렇게 설계되었는지 알고 있는 개발자는 많지 않다. 이 글은 Java의 정렬 함수가 어떤 로직으로 동작하며, 왜 특정 알고리즘을 선택하고 있는지를 깊이 있게 분석한다.

1. Java의 정렬 함수 종류와 알고리즘

✅ 기본형 배열: Dual-Pivot Quicksort

📌 핵심 개념

Java 7부터 기본형 배열 정렬에는 Dual-Pivot Quicksort가 사용된다. 이는 기존의 단일 피벗 퀵소트보다 더 빠르게 동작하도록 개선된 정렬 방식이다.

⚙️ 작동 방식

  • 두 개의 피벗을 선택해 배열을 세 부분으로 분할
    • 피벗1보다 작은 영역 / 피벗1과 피벗2 사이 / 피벗2보다 큰 영역
  • 각 영역을 재귀적으로 정렬

📈 성능

  • 최선 시간 복잡도: O(n log n)
  • 평균 시간 복잡도: O(n log n)
  • 최악 시간 복잡도: O(n^2) (피벗 선택이 실패할 경우)
  • 공간 복잡도: O(log n) (재귀 스택)

✅ 객체 배열 및 컬렉션: TimSort

📌 TimSort란?

TimSort는 Insertion Sort + Merge Sort의 하이브리드 정렬 알고리즘이다. Python에서도 기본 정렬로 사용되며, Java 7부터 객체 배열과 리스트 정렬에 채택되었다.

⚙️ TimSort 작동 원리

  1. 배열을 일정 크기(run) 단위로 분할
  2. 각 run은 Insertion Sort로 정렬
  3. 정렬된 run들끼리 Merge Sort 방식으로 병합
Arrays.sort(Object[] arr);        // 내부적으로 TimSort
Collections.sort(List<T> list);   // 내부적으로 Arrays.sort(list.toArray()) → TimSort

📈 성능

  • 최선 시간 복잡도: O(n) (이미 정렬된 경우)
  • 평균 시간 복잡도: O(n log n)
  • 최악 시간 복잡도: O(n log n)
  • 공간 복잡도: O(n)

2. 기본형 배열 정렬에 Dual-Pivot Quicksort를 사용하는 이유

1. 실제로 매우 빠르다 (성능 최적화)

  • 기존의 단일 Pivot Quicksort보다 약 10~20% 빠른 성능을 보임
  • 동일한 O(n log n) 복잡도지만, 더 고른 분할, 비교 횟수 감소, 캐시 활용도 증가 덕분에 속도 향상

2. 메모리 사용이 매우 효율적 (in-place 정렬)

  • 추가 배열 없이, 입력 배열 자체를 정렬
  • 공간 복잡도는 O(log n) (재귀 스택 용도)

-> Java는 기본형 배열이 주로 대량 데이터 처리에 쓰이는 점을 고려해 -> 추가 메모리 할당이 없고 빠른 정렬이 매우 중요함

3. Stable 정렬이 필요하지 않다

  • 기본형 배열은 숫자 값 그 자체만 정렬 대상임
  • 동일한 값의 상대 순서를 보존할 필요 없음 -> 안정 정렬 필요 X -> TimSort 같은 안정 정렬은 오히려 불필요한 오버헤드

4. 배열 접근과 교환이 빠르다 (primitive type 특성)

  • 기본형 배열은 객체 배열보다 캐시 효율이 훨씬 높음
  • int, long, double은 메모리에 연속적으로 저장되어 있어 순차 접근이 빠름
  • Dual-Pivot Quicksort는 메모리 접근 패턴이 순차적이어서 CPU 캐시와 잘 맞음

기본형 배열은 값 자체가 연속된 메모리 공간에 저장된다. 반면, 객체 배열은 참조(reference) 배열이다. 따라서, 기본형은 CPU가 예측 가능한 방식으로 메모리를 선형 접근할 수 있다. 반면에 객체 배열은 참조를 따라가야 하므로, 무작위(Random) 접근이 발생하고 캐시 미스가 증가한다.

순차적 메모리 접근 -> CPU는 인접한 데이터도 캐시에 미리 불러옴 (Spatial Locality) 따라서 arr[0]을 읽을 때, arr[1], arr[2]도 이미 캐시에 있음 -> 접근 시 거의 항상 캐시에 있음 -> 속도 매우 빠름

5. 다른 알고리즘에 비해 구현이 간결하고 고성능에 안정적

  • Merge Sort: 안정 정렬이지만 추가 메모리 O(n) 필요 -> 부적합
  • Heap Sort: O(n log n)이지만 실제 성능이 떨어지고 구현 복잡도 높음
  • TimSort: 객체 배열에는 유리하지만, 기본형엔 안정성 불필요 + 오버헤드 존재

-> Dual-Pivot Quicksort는 모든 측면에서 기본형 배열에 이상적

3. 객체 배열 및 리스트 정렬에 TimSort를 사용하는 이유

1. 안정 정렬(Stable Sort)이 필수적이기 때문

📌 객체 배열은 단순 값이 아니라 속성(필드)을 기반으로 정렬됨

-> 동일한 기준 값일 경우에도 기존 순서(입력 순서)가 의미를 가질 수 있음 -> Quicksort 계열은 안정 정렬을 보장하지 못함, TimSort는 항상 보장

2. 이미 정렬된 데이터에 매우 강함

TimSort는 입력 배열에 이미 정렬된 부분(run)을 감지하여 Insertion Sort로 빠르게 처리 -> 실무 데이터에서 자주 발생하는 부분 정렬된 상태에 최적화

📌 예시:

  • 게시글 시간순 정렬 후, 조회수로 다시 정렬
  • 사용자 이름순 정렬 후, 등급별 정렬

-> 정렬이 덜 필요함 -> Insertion Sort만으로도 O(n) 성능 가능

3. 다단계 정렬(복합 정렬)에 안정성이 중요

예를 들어:

list.sort(comparing(User::getLevel)); // 1차 정렬
list.sort(comparing(User::getName));  // 2차 정렬

-> 이때 앞선 정렬 기준이 깨지면 다단계 정렬 자체가 무의미 -> **TimSort의 stable sort 특성 덕분에 정렬 간 순서가 보존됨

4. 객체는 추가 메모리 사용에 대한 부담이 적음

  • TimSort는 내부적으로 O(n)만큼의 임시 배열을 사용 (Merge 과정에서)
  • 객체 배열은 일반적으로 기본형보다 크기가 작고, reference를 정렬하므로 -> 복사 비용이 크지 않음
  • Stable + 안전한 O(n log n) 보장이 더 중요

객체 배열은 내부 요소가 값이 아니라 참조로 구성되어 있으므로, TimSort에서 사용하는 임시 배열 복사 시에도 참조값만 이동하면 되며, 이는 기본형 배열보다 복사 비용과 메모리 부담이 낮다.

5. 다른 정렬에 비해 실전에서 예외 케이스가 적음

알고리즘 문제점
QuickSort 불안정 정렬, O(n²) 위험
MergeSort 안정 정렬이지만 항상 O(n log n) / 캐시 효율 ↓
HeapSort 느리고 불안정, 거의 실무 사용 X
TimSort 안정성 + 최적화된 실전 성능 + 실수 방지용 조건 포함

-> 실제 배포 환경에서 실패 확률이 거의 없는 신뢰성 높은 알고리즘

4. 왜 TimSort는 Insertion Sort와 Merge Sort를 결합했는가?

TimSort는 각각의 장점을 취했다:

🔹 Insertion Sort가 작은 구간에서 빠른 이유

  • 간단한 이동 연산: 인접 값만 밀어 넣음
  • 이미 정렬된 경우 성능 극대화 (O(n))
  • 함수 호출 오버헤드 없음

🔹 Merge Sort의 장점

  • 일관된 O(n log n) 성능 보장
  • Stable Sort: 동일 값 간 상대 순서 유지
  • 메모리에 모두 올릴 수 없는 대용량 데이터도 디스크 기반 순차 접근으로 안정적으로 정렬 가능

TimSort는 이 두 가지를 상황에 따라 동적으로 적용해 최적의 성능을 확보한다.

댓글남기기