java의 arrays.sort 메서드는 어떤 정렬을 사용할까요?

 java의 Array.sort는 어떤 정렬 알고리즘을 쓸까요? primitive type을 정렬하는 경우와, 그렇지 않은 경우에 쓰는 알고리즘이 다릅니다. 어떻게 다른지 간단하게 보도록 하겠습니다. java8 기준으로 작성되었음을 참고하시면 됩니다.

 

---

 먼저 primitive type을 정렬할 때 어떻게 동작할까요? Array.class 안으로 들어가 보겠습니다.

 

 int형을 저장해 놓은  배열을 정렬하려는 경우보시면, rangeCheck를 하고, DualPivotQuickSort로 들어간다는 것을 알 수 있습니다. short형은 어떨까요?

 

 

 마찬가지입니다. DualPivotQuickSort 안으로 들어가 보겠습니다.

 

 

 먼저, int형 배열을 정렬하는 경우입니다. QuickSort_ThreasHold보다 작으면 sort를 호출합니다. 주석에 달린 대로, QuickSort 함수를 부릅니다. 다음에 run 배열이 하나 더 있습니다. 그리고 MAX_RUN_COUNT도 있는데요. 이것이 무슨 역할을 하는지는 121번째 줄부터 보면 대략적으로 알 수 있습니다.

 

 

 123번째 줄의 for 루프 안에 if, else if, else로 연결되어 있는 블록이 있습니다. 그리고, 144번째 줄의 if가 있는데요. 이 절들을 잘 해석해 보면, 증가 상태, 감소 상태, 같은 상태 이렇게 3가지가 있는 것을 알 수 있습니다. 상태가 바뀔 때 마다, while loop가 끝납니다. 다시 말해, 이렇게 해석을 할 수 있습니다.

 

 구간이 gugan 개로 나뉜다. 만약에 감소하는 구간이면, 순서를 바꿔서 '증가' 하는 구간으로 만들 수 있을 겁니다.

 

 

 이런 식으로 전처리를 할 수 있습니다. 그 구간이 일정한 갯수를 넘어가면, 145번째 줄의 sort 함수를 수행합니다. 그렇지 않으면, 밑에 있는 코드들을 수행하는데요. 이 부분은 여기에서 굳이 다루지는 않겠습니다. 간단하게 요약하면, 구간별로 나누어진 데이터들을 합치는 작업을 합니다.

 

 

 145번째 줄의 sort 내부로 들어가 보면, Dual pivot Quicksort 라는 문구가 눈에 들어옵니다.

 

 

 이것은 배열의 크기가 일정 이하이면, Insertion sort를 수행합니다. int형은 -2147483648부터 2147483647까지 나타날 수 있기 때문에, count sort로 커버가 되지 않습니다. 만약에 cover가 된다면 어떨까요? 예를 들자면, byte나, char나, short는 counting sort를 쓸 수 있을 만큼 가능 집합의 크기가 작습니다.

 

 

 그러면, 일정 크기 이상인 경우에 count sort를 수행합니다. 그렇지 않으면 dual pivot quick sort를 수행합니다. 카운팅 정렬이 복잡도가 더 좋은 거 같은데 왜 퀵 소트를 사용할까요? 이유는 간단합니다. 예를 들어, 길이 10인 short 배열을 정렬한다고 해 보면, 나오는 값의 갯수는 많아봐야 10개입니다.

 

 그런데 계수 정렬을 하면, 65536개의 임시 배열을 새로 생성해야 합니다. 그럴 바에야, 차라리 insertion sort나 quick이 낫습니다. 최악의 경우에도 O(배열크기^2)이기 때문입니다. 65536 vs 100. 상식적으로 후자를 택하는 게 이득일 겁니다.

 

 

 primitive type일 때 정리를 해 보았습니다. 군청색으로 표시한, byte나 char, short인 경우, 집합의 크기가 작기 때문에, 기본적으로 꽤 큰 배열인 경우, count sort부터 해 본다. 그렇지 않은 경우에, 먼저 dual pivot quick sort를 수행한다. 정도만 기억하셔도 좋을 듯 싶습니다.

 

 무조건 quick을 쓴다. 이건 아닙니다.

 

---

 그러면 정렬 대상이 Object인 경우에는 어떻게 동작할까요?

 

 모든 객체는 Object입니다. 따라서, Object를 정렬하는 경우, 위에 있는 것이 호출됩니다. LegecyMergeSort.userRequested가 true인 경우에 legacyMergeSort가 호출이 됩니다. 그렇지 않으면 TimSort를 부릅니다. 1244번째 줄에 있는 메소드 내부로 들어가 보겠습니다.

 

 

 그러면, mergeSort만 덩그러니 놓여져 있음을 알 수 있습니다. 메서드 위에 주석으로 To be removed in a future release라고 되어 있는데요. 이는 발전된 버전에서는 이 메서드를 쓰지 않는다 (혹은 추후에 쓰지 않을 예정이라)는 의미입니다.

 

 

 만약에, Object type의 정렬을, MergeSort로 하고 싶다면, property의 java.util.Arrays.useLegecymergeSort를 true로 설정해야 합니다. 그러면, Tim 대신에 Merge를 쓰게 됩니다만. legacy merge가 제거 된 경우에는 소용이 없을 거고요.

 

 

 요약하자면, Object array를 정렬하는 경우에 따로 legacy한 merge를 쓰겠다는 설정을 하지 않으면 Tim sort를 시킨다. 정도만 알아두시면 됩니다. 팀 소트에 대한 글은 tim sort라는 키워드로 검색하시면 괜찮은 글이 많으므로 한 번 정도 보시는 게 좋겠습니다.