[Java] Arrays.sort() 어떤 정렬 알고리즘을 쓸까?

정렬 알고리즘 구현을 공부하던 중, 자바의 정렬 알고리즘이 어떻게 구현되어 있는지 궁금해져서 조사해 보았습니다. 그 결과는 다음과 같습니다.

원시타입: DualPivotQuickSort를 사용합니다. 이는 Quick Sort의 변형으로, 배열의 크기에 따라 다른 정렬 알고리즘과 섞어 사용됩니다. 자세한 내용은 여기 참조: Java Arrays.sort() 분석
객체타입: 이전에는 MergeSort를 사용했으나 현재는 TimSort를 사용합니다. TimSort는 InsertionSort와 MergeSort의 조합입니다. Collections.sort 또한 내부적으로 Object[]로 변환하여 Arrays.sort()를 사용합니다.

 

원시타입 DualPivotQuickSort

객체타입 TimSort (예전에는 MergeSort 를 쓴 것으로 추정됨)

 

TimSort 는 왜 Insertion Sort 를 썼을까?

출처 - 네이버 D2

TimSort가 Insertion Sort를 포함하는 이유는 '참조 지역성' 때문입니다. 참조 지역성은 CPU가 데이터를 캐싱하는 방법과 연관이 있습니다. CPU는 효율적으로 다음 명령을 처리하기 위해 자주 참조될 것 같은 데이터를 미리 캐싱합니다. 참조 지역성에는 '시간 지역성'과 '공간 지역성' 두 가지 유형이 있습니다. 시간 지역성은 최근 조회된 데이터를 다시 조회할 가능성이 높다고 판단할 때 캐싱하는 것을 말하며, 공간 지역성은 방금 조회된 데이터의 인접 데이터도 곧 사용될 것으로 예측하고 캐싱하는 것을 의미합니다.

 

1. 시간 지역성 : "방금 조회한 데이터는 분명 또 조회될거 같다! 캐싱해두자"
2. 공간 지역성 : "방금 조회한 데이터의 다음 데이터는 분명 다음에 조회될거 같다! 캐싱해두자" (ex. for 문을 돌때 idx = i 일 때 i+1 도 미래에 참조될 것이라고 예측하고 저장하는 것은 합리적인 행위이다)

이 글에서 말하는 지역성은 공간 지역성입니다.

 

Insertion Sort 와 Heap Sort 를 비교하면 Insertion Sort 의 참조 지역성이 좋음이 보입니다. 

Heap Sort 는 idx = i 에서 자식 노드를 접근하기 위해 idx = i*2, i*2+1 로 멀리 떨어진 곳을 조회하는 반면에 Insertion Sort 은 idx =i 에서 바로 옆 i+1로 접근하기 때문에 공간 지역성 면에서 유리합니다.

HeapSort (먼 곳을 참조하게 됨)

Insertion Sort (바로 옆을 참조하게 됨)

Insertion Sort 를 Quick Sort 와 비교해보도록 하자. 각 정렬의 참조 지역성을 고려한 상수 C 라고 할 때

Insertion Sort 의 실제 실행 속도 : Ci​×n^2
Quick Sort 의 실제 실행 속도 : Cq​×nlogn

작은 n 에 대해서는 Ci​×n2<Cq​×nlogn 즉, Quick Sort 보다 Insertion Sort 가 더 빠르다.

따라서 작은 덩어리로 만들어 먼저 덩어리에 대해 Insertion Sort 를 먼저 해주고 모든 덩어리에 대해 Merge Sort 를 해주는 최적화를 선택한 것이다.  

 

왜 원시타입과 객체타입의 정렬 알고리즘이 다를까?

원시 타입과 객체 타입에서 사용되는 정렬 알고리즘의 선택은 '안정성' 차이에 기인합니다. 예를 들어, 원시 타입의 경우 Quick Sort와 같은 unstable 정렬이 문제가 되지 않습니다. 그러나 객체 타입의 경우, 같은 값을 가진 다른 객체들의 순서가 유지되어야 할 필요가 있어, stable한 정렬이 중요합니다. 따라서 TimSort와 같은 stable한 정렬 방식이 선택되었습니다.

 

예를 들어, 원시 타입의 경우 [1,1,2,3] 를 정렬할 때 1 과 1의 순서가 바뀌어도 신경 쓸 이슈가 아닙니다. 그러나 객체 타입의 경우 [Student(name="a",age=1), Student(name="b", age=1), Student(name="c", age=2), Student(name="d", age=3)] 를 age 로 정렬한다고 했을 때 a, b 의 순서가 입력 순서에 따라 정렬결과가 바뀔 수 있습니다. 

 

 

참고

https://d2.naver.com/helloworld/0315536

https://cs-vegemeal.tistory.com/53

https://ongveloper.tistory.com/385