Sort

비교표

정렬 알고리즘	최선	평균	최악	제자리(In-place)	안정(Stable)
버블 정렬	O(n)	O(n²)	O(n²)	✅	✅
선택 정렬	O(n²)	O(n²)	O(n²)	✅	❌
삽입 정렬	O(n)	O(n²)	O(n²)	✅	✅
퀵 정렬	O(n log n)	O(n log n)	O(n²)	✅	❌
병합 정렬	O(n log n)	O(n log n)	O(n log n)	❌(추가 O(n))	✅
Timsort	O(n)	O(n log n)	O(n log n)	❌(추가 O(n))	✅

용어 한 줄 요약

• 제자리 정렬: 추가 메모리 거의 없음(스택/소량의 보조 배열 제외).
• 안정 정렬: 동일 키의 상대적 순서가 유지됨(예: 정렬 후에도 같은 값끼리 입력 순서 그대로).

---

Java Arrays.sort()는 내부적으로 무엇을 쓰나?

1) 원시(숫자) 타입 배열

• Dual-Pivot QuickSort 사용

  • 연속 메모리 + 빠른 스왑 → 제자리로 매우 효율적
  • 동일 값의 상대 순서 유지 중요도가 낮아 불안정이어도 무방

• 대표 타입: int[], long[], double[] 등

2) 객체 배열

• Timsort 사용 (실제 구현: 병합/삽입 혼합 기반)

  • 비교 연산 비용이 큰 객체에는 비교 횟수를 줄이는 전략이 유리
  • 최악도 O(n log n) → 예측 가능한 성능
  • 동일 값 순서가 중요한 도메인 고려해 안정 정렬

• 대표 타입: String[], Integer[], 임의의 Comparable[]

팁

• 리스트라면 Collections.sort(list) 또한 내부적으로 Timsort 계열을 사용(안정).
• 이미 “부분적으로 정렬된(run이 많은)” 데이터는 Timsort에서 거의 O(n) 에 근접.

---

핵심 요약

• 데이터가 거의 정렬됨 → 삽입 정렬 또는 Timsort가 이득.
• 메모리 제약 큼 → 퀵 정렬 같은 제자리 정렬 선호.
• 안정성이 필요(2차 키 정렬 등) → 병합 정렬·Timsort.
• 항상 최악도 빠르게 → 병합 정렬·Timsort.

---