Java에서 컬렉션 sort 동작 방식

컬렉션에 담겨있는 요소의 타입에 따라 Java 컬렉션의 sort가 달라지는 걸 몰랐다.

 

그냥 timsort 아닌가? 라고 생각을 했었다.

 

아니였다.

 

원시타입의 경우에는 Dual-Pivot Quicksort를 쓴다.

객체타입의 경우에는 TimSort를 쓴다.

 

그렇다면 왜 타입에 따라 다르게 sort를 할까?

 

정렬 대상을 원시 타입(primitive)과 객체 타입(object)으로 나누어 다른 정렬 알고리즘을 사용하는 것은 성능 최적화와 안정성(Stability)이라는 두 마리 토끼를 잡기 위해서이다.

 

좀 더 자세히 알아보자

 

 

1. 듀얼 피벗 퀵 정렬 (Dual-Pivot Quicksort)

대상: Arrays.sort(int[]), Arrays.sort(double[]) 등 원시 타입 배열

이 알고리즘은 Java 7부터 원시 타입 배열의 기본 정렬 알고리즘으로 채택되었다.

 

클래식 퀵 정렬 (피벗 1개)

먼저 우리가 아는 일반적인 퀵 정렬은 1개의 피벗(Pivot)을 선택

1. 배열에서 피벗 하나를 고른다.
2. 피벗보다 작은 값들은 왼쪽, 큰 값들은 오른쪽으로 분할(Partition)한다.
3. 왼쪽과 오른쪽 두 부분에 대해 이 과정을 재귀적으로 반복한다.

 

 듀얼 피벗 퀵 정렬 (피벗 2개)

이름처럼, 듀얼 피벗 퀵 정렬은 2개의 피벗(P1, P2)을 사용합니다. (단, P1 <= P2 여야 함)

1. 배열에서 피벗 2개(P1, P2)를 고른다.
2. 배열을 3개의 파티션으로 분할한다.
   • Part 1: P1보다 작은 값들
   • Part 2: P1 이상, P2 이하인 값들
   • Part 3: P2보다 큰 값들
3. 이 3개의 파티션에 대해 재귀적으로 정렬을 반복한다.

 왜 원시 타입에 사용할까?

• 압도적인 속도: 3개 파티션으로 나누는 것이 2개로 나누는 것보다(데이터가 무작위일 경우) 이론적, 실증적으로 더 빠르다. 더 효율적으로 데이터를 거르기 때문에 재귀 호출의 깊이가 줄어든다.
• 안정성(Stability) 불필요: 퀵 정렬은 불안정 정렬(Unstable Sort)이다. 즉, 같은 값의 순서가 바뀔 수 있다. 하지만 원시 타입 (ex int 5와 int 5)은 서로 구분이 불가능하므로 순서가 바뀌어도 아무런 문제가 없다.
• 데이터 이동 비용이 저렴: 원시 타입은 값을 복사하고 교환(swap)하는 비용이 매우 저렴하다.

단점은 최악의 경우 O(n^2)의 시간 복잡도를 가질 수 있지만 (이미 정렬된 경우 등), Java는 피벗 선택을 정교하게 하여 이를 회피한다.

---

2. 팀 정렬 (Timsort)

 대상: Arrays.sort(Object[]), Collections.sort(List<T>) 등 객체 배열 및 컬렉션

Timsort는 파이썬의 기본 정렬 알고리즘을 만든 Tim Peters에 의해 고안되었으며, Java 7부터 객체 정렬에 도입되었다. (그 이전에는 병합 정렬(Merge Sort)을 썼다.)

Timsort는 삽입 정렬(Insertion Sort)과 병합 정렬(Merge Sort)을 결합한 하이브리드(Hybrid) 및 적응형(Adaptive) 알고리즘이다.

 동작 방식 (2단계)

1. Phase 1: 'Run' 생성 (삽입 정렬 활용)
   • Timsort는 실제 세계의 데이터가 완전히 무작위가 아니라 부분적으로 정렬된 경우가 많다는 점에 착안한다.
   • 배열을 스캔하며 이미 정렬된 연속된 부분(오름차순 또는 내림차순)을 찾습니다. 이를 Run이라고 부른다.
   • 만약 Run의 길이가 너무 짧으면 (ex 32개 미만), 그 부분에 삽입 정렬을 수행하여 강제로 최소 길이의 Run을 만든다.
   • 이유: 삽입 정렬은 데이터가 적거나 거의 정렬된 상태일 때 O(n)에 가까운 매우 빠른 속도를 낸다.
2. Phase 2: 'Run' 병합 (병합 정렬 활용)
   • 이제 배열은 여러 개의 정렬된 Run들로 쪼개져 있다.
   • 이 Run들을 병합 정렬 방식으로 합쳐나간다.
   • 일반 병합 정렬과 달리, Timsort는 스택(Stack)을 사용해 인접한 Run들의 크기를 비교하며 매우 지능적이고 효율적인 순서로 병합을 수행한다. (ex "Galloping" 기법)

💡 왜 객체 타입에 사용할까요?

• 안정 정렬 (Stable Sort) 보장: 가장 중요한 이유이다. 객체는 (이름: "Alice", 나이: 30), (이름: "Bob", 나이: 30) 처럼 데이터가 복합적하다 만약 '나이'로 정렬할 때, 나이가 같은 "Alice"와 "Bob"의 기존 순서가 바뀌면 안된다. Timsort는 병합 정렬을 기반으로 하므로 이 안정성을 보장한다.
• 적응형 (Adaptive): 이미 정렬된 데이터가 많을수록 $O(n)$에 가까운 속도를 낸다.
• 비교 비용 최소화: 객체 정렬은 compareTo()나 compare() 메서드를 호출한다. 이 메서드 내부는 단순 숫자 비교가 아니라 복잡한 로직일 수 있어 비용이 비싸다. Timsort는 최악의 경우에도 O(n \log n)의 비교 횟수를 보장하여 비싼 비교 연산을 최소화한다.
• 메모리 효율: 병합 정렬의 단점인 추가 메모리 공간(O(n))이 필요하지만, Timsort는 이를 최적화하여 필요한 임시 공간을 O(n)보다 적게 (최선 O(1), 보통 O(logn) ~ O(n/2)) 사용하려 노력한다.

---

📊 요약 비교

특징	듀얼 피벗 퀵 정렬 (Dual-Pivot Quicksort)	팀 정렬 (Timsort)
주요 대상	원시 타입 배열 (int[], long[]...)	객체 배열 (Object[]), 컬렉션 (List)
기반 알고리즘	퀵 정렬 (Quick Sort) 변형	삽입 정렬 (Insertion) + 병합 정렬 (Merge)
안정성 (Stability)	불안정 (Unstable)	안정 (Stable) (필수!)
시간 복잡도	평균 O(nlogn), 최악 O(n2)	최선 O(n), 최악 O(nlogn)
핵심 특징	속도 (빠른 파티셔닝, 저렴한 데이터 이동)	안정성 및 적응성 (비싼 비교 최소화)

 

결론적으로, Java는 '구분이 안 되고 교환이 싼' 원시 타입에는 가장 빠른 듀얼 피벗 퀵 정렬을, '구분이 필요하고 비교가 비싼' 객체 타입에는 안정성을 보장하고 실데이터에 강한 Timsort를 사용하는 매우 영리한 전략을 취하고 있다.