Wrapper Type일 경우 -> legacyMergeSort, ComparableTimSort 알고리즘 적용
Primitive Type일 경우 -> DualPivotQuickSort 알고리즘 적용
Wrapper Type일 경우 Arrays.sort()Primitive Type일 경우 Arrays.sort()
Collections.sort()
내부를 확인하면, legacyMergeSort()와 TimSort() 알고리즘 적용
TimSort 알고리즘
Timsort is a hybrid stable sorting algorithm, derived from merge sort and insertion sort, designed to perform well on many kinds of real-world data.
In the worst case, Timsort takes comparisons to sort an array of n elements. In the best case, which occurs when the input is already sorted, it runs in linear time, meaning that it is an adaptive sorting algorithm. - wikipedia
DualPivotQuickSort 알고리즘 -> 평균의 경우 : O(nlogn) / 최악의 경우 : O(n^2)
Timsort 알고리즘 -> 평균의 경우 : O(nlogn) / 최악의 경우 : O(nlogn)
근데 왜 DualPivotQuickSort 알고리즘을 Object타입 정렬에 사용하지 않는가?
정렬 안정성 때문이다. DualPivotQuickSort는 일반 QuickSort와 같이 정렬 안정성을 보장해주지 않는다고 한다.
