[210726] Collections.sort & Arrays.sort

배열 정렬을 하다 ArrayList를 사용한 배열을 오름차순으로 정렬하던 중
Arrays.sort() 사용이 불가능했다..

검색해 본 결과 java 내부에서 처리하는 로직이 다름

결론부터 정리하면

일반적인 배열은 Arrays.sort() 사용
List는 Collections.sort() 사용

Arrays.sort()

내부를 살펴보면

import java.util.Arrays
// 듀얼피봇 퀵정렬(DualPivot-QuickSort)
public static void sort(int[] a) {
    DualPivotQuicksort.sort(a, 0, a.length - 1, null, 0, 0);
}

듀얼피봇 퀵정렬?
-> 일반적인 퀵정렬과는 다르게 피봇을 2개를 두고 3개의 구간을 만들어 퀵정렬 진행
-> 이 방식은 랜덤 데이터를 평균적으로 퀵정렬보다 좋은 성능을 냄

Collections.sort()

Arrays.sort()와 엄밀하게 다르다
Collections.sort()의 코드 내부를 보면

public static void sort(Object[] a) {
    if (LegacyMergeSort.userRequested)
        legacyMergeSort(a);
    else
        ComparableTimSort.sort(a, 0, a.length, null, 0, 0);
}

레거시로 합병정렬과 Tim 정렬을 사용하고 있다
+) 합병정렬 / Tim 정렬
합병정렬은
Tim 정렬은 삽입(Insertion) 정렬과 합병(Merge) 정렬을 결합하여 만든 정렬

Collections.sort() vs Arrays.sort()

두 정렬을 사용했을 때 사용하는 알고리즘이 왜 다를까?
-> 참조 지역성 원리(Local of Reference) 때문
--> 동일한 값 또는 해당 값의 근처에 있는 스토리지 위치가 자주 액세스되는 특성
--> 이 참조 지역성 원리는 CPU의 캐싱 전략에 영향을 미침
--> 즉, CPU가 데이터를 액세스하며 해당 데이터만이 아니라 인접한 메모리에 있는 데이터 또한 캐시 메모리에 함께 올려둠

정렬의 실제 동작 시간은 C * 시간복잡도 + a

a는 상대적으로 무시 가능, 하지만 곱해지는 C의 영향도는 고려
-> C 값이 바로 참조 지역성 원리가 영향을 미침

Array는 메모리에 값들이 연속적인 주소를 갖고 있기에 C 값이 낮음
-> 그래서 참조 지역성이 좋은 퀵 정렬을 사용하면 성능이 괜찮음

하지만 Collection은 List를 기준으로, 메모리간 인접한 ArrayList 뿐만 아니라 메모리적으로 산발적인 LinkedList도 함께 존재
-> 따라서 참조 인접성이 좋지 않고, C 값이 상대적으로 높음
-->이럴 때 퀵정렬 보다는 Tim 정렬(합병정렬 + 삽입정렬)을 이용하는 게 성능에 좋음