Arrays.sort()

java의 대표적인 정렬 메서드인 Arrays.sort()는 static 메서드로 인스턴스를 생성하지 않고 바로 사용할 수 있다. 인자로는 char, int, boolean 등의 primitive 타입과 reference 타입인 배열을 전달 할 수 있데, 두 경우 사용되는 알고리즘이 다르다.

primitive 타입

---

primitive 타입인 경우 DualPivotQuicksort 알고리즘이 사용된다. 이는 QuickSort에서 Pivot(중심축)을 2개 사용하는 방식으로 이상적인 경우 O(nlogn)의 시간 복잡도가 발생하지만 이미 정렬된 배열의 경우 O(n^2)의 시간 복잡도가 발생한다.

또한 Array.sort()에 사용되는 DualPivotQuicksort.sort()는 다음과 같이 배열의 크기에 따라 다양한 정렬 알고리즘을 사용한다.

• 배열의 크기가 286 이상일 경우 MergeSort
• 배열의 크기가 286 보다 작은 경우 QuickSort(DualPivotQuicksort)
• 배열의 크기가 47 보다 작은 경우 InsertionSort
• byte 배열의 크기가 29 보다 큰 경우 CountingSort
• short, char 배열의 크기가 3200 보다 큰 경우 CountingSort

Reference 타입

---

Reference 타입(Object array)을 정렬하는 경우에 따로 legacy한 MergeSort알고리즘을 쓰겠다는 설정을 하지 않으면 TimSort 알고리즘을 사용한다..