• Arrays.sort(int[] a) - > DualPivotQuickSort.sort()
• Arrays.sort(Object[] a) -> ComparableTimSort.sort()

팀 정렬

• 합병정렬, 삽입정렬이 혼용된 하이브리드 정렬 알고리즘 합병정렬을 기반으로 구현, 일정 크기 이하의 부분 리스트에 대해 이진 삽입 정렬을 활용
• 안정정렬
• 최선의 경우 O(N)
• 최악의 경우 O(NlogN)

등장배경

• 현실 데이터를 종류와 상관 없이 최적으로 정렬을 수행하는 것 각 정렬 알고리즘은 장단점이 있기 때문에 장점은 가져오고 단점을 보완해야함
  • 안정정렬이 중요
  • 최악의 경우에도 성능 보장 필요
• 퀵 정렬은 빠르지만 불안정 정렬이고 특정 경우 성능이 나쁘다.
• 힙 정렬은 참조 지역성이 떨어지고 데이터가 클수록 성능이 나쁘다.
• 합병 정렬은 추가적인 메모리가 필요하고 퀵 정렬에 비해 느리다.

병합정렬

느리고 메모리 사용량이 많은 걸 어떻게 개선?

• 시간이 오래 걸림 -> 삽입 정렬을 활용해 개선
  • 삽입 정렬은 인접한 메모리와 비교하기 때문에 참조 지역성이 좋음
• 메모리 사용량이 많음 -> 최적화 기법 활용
  • 전체에 대해 모두 병합하는 것이 아닌 정렬이 필요한 부분만 병합하면서 메모리 사용량을 줄임