TimSort
: Merge Sort + Insertion Sort를 결합한 하이브리드 정렬 알고리즘.
: Java의 Arrays.sort()에서 실제로 사용되는 정렬 알고리즘
즉, 자바에서 Arrays.sort()를 쓰면 내부적으로 TimSort가 작동.
✅ Merge Sort와 Insertion Sort를 섞은 이유
- Merge Sort: 시간 복잡도는 항상 O(n log n )으로 안정적이지만, 작은 데이터에는 다소 느림
- Insertion Sort: 시간 복잡도는 O(n^2)이지만, 데이터가 거의 정렬되어 있을 때는 매우 빠름
⇒ 그래서 TimSort는 이미 정렬돼 있는 부분은 Insertion Sort로 다듬고, 나머지는 Merge Sort처럼 합쳐서 정렬한다.
✅ TimSort의 특징
| 특징 | 설명 |
|---|
| stable Sort | 같은 값이 있을 때, 기존 순서 유지 |
| 실제 데이터에 강함 | 이미 정렬된 부분이 많을수록 더 빠름 |
| 시간 복잡도 | 평균, 최악: O(n log n) / 최선: O(n) |
✅ Java에서 사용되는 곳
| Java 메서드 | 사용 알고리즘 |
|---|
| Arrays.sort(Object[]) | TimSort |
| Arrays.sort(int[]) | Dual-Pivot QuickSort (Primitive 타입엔 TimSort 사용X) |
