Arrays.sort() Collections.sort()에서 사용되는 알고리즘

Arrays.sort() Collections.sort()에서 사용되는 알고리즘

🔴 Arrays.sort()
배열을 정렬하는 Arrays.sort에 대해 알아보자.
Arrays,sort의 코드를 확인했을 때 아래와 같이 주석과 코드가 나왔다. 이를 토해서 보면 듀얼피봇 퀵정렬(Dual-Pivot QuickSort)를 사용한다고 명시되어 있는 것을 확인할 수 있다.

/* * * Sorts the specified array into ascending numerical order. * * <p>Implementation note: The sorting algorithm is a Dual-Pivot Quicksort * by Vladimir Yaroslavskiy, Jon Bentley, and Joshua Bloch. This algorithm * offers O(n log(n)) performance on many data sets that cause other * quicksorts to degrade to quadratic performance, and is typically * faster than traditional (one-pivot) Quicksort implementations. * * @param a the array to be sorted */ 
public static void sort(int[] a) {
    DualPivotQuicksort.sort(a, 0, a.length - 1, null, 0, 0); 
}

듀얼피봇 퀵정렬은 일반적인 퀵정렬과는 다르게 피봇을 2개 두고 3개의 구간을 만들어 퀵정렬을 진행한다.
이 정렬 방식은 랜덤 테이터에 대해서 평균적으로 퀵정렬보다 좋은 성능을 낸다고 알려져 있다.

---

🔴Collections.sort
Collections의 정렬을 보면, Arrays.sort()와 동일한 정렬을 사용할 것 같으나 다른 정렬을 사용한다.

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

레거시로 합병정렬과 Tim 정렬을 사용하고 있는 사실을 알 수 있다.
Tim 정렬은 삽입(Insertion) 정렬과 합병 (Merge) 정렬을 결합하여 만든 정렬이다. java 7부터 Time 정렬을 채택했다고 한다.

---

🔴 Arrays.sort() vs Collections.sort()

그렇다면 Arrays를 정렬했을 때와 Collections를 정렬했을 때 왜 사용하는 알고리즘이 다를까?
그 이유는 참조 지역성 원리(Local of Reference)에 있다. 참조 지역성의 원리란 동일한 값 또는 해당 값의 근처에 있는 스토리지 위치가 자주 액세스 되는 특징을 말한다.
이 참조 지역성의 원리는 CPU의 캐싱 전략에 영향을 미친다. 즉, CPU가 데이터를 액세스하면서 해당 데이터만이 아니라 인접한 메모리에 있는 데이터 또한 캐시 메모리에 함께 올려둔다.

정렬의 실제 동작은 C * 시간복잡도 + a라고 한다. a는 상대적으로 무시할 수 있는데 곱해지는 C의 영향도는 고려해야한다. 이 C라는 값이 바로 참조 지역성 원리가 영향을 미친다.

Array는 메모리적으로 각 값들이 연속적인 주소를 가지고 있기 때문에 C의 값이 낮다. 그래서 참조 지역성이 좋은 퀵 정렬을 이용하면 충분한 성능을 제공할 수 있다고 한다.
하지만, Collection은 List를 기준으로 봤을 때 메모리 간 인접한 ArrayList뿐만 아니라 메모리적으로 산발적인 LinkedList도 함께 존재한다. 따라서 참조 인접성이 좋지 않고 C의 값이 상대적으로 높다고 한다.
이럴 때는 퀵 정렬보다는 합병 정렬과 삽입 정렬을 병합한 Tim 정렬을 이용하는 게 평균적으로 더 좋은 성능을 기대할 수 있다고 한다.

---

Arrays.sort() vs Collections.sort()
https://sabarada.tistory.com/138

퀵정렬 상세설명 :
https://lotuslee.tistory.com/29

Tim정렬 상세설명 :
https://d2.naver.com/helloworld/0315536