Array의 정렬 알고리즘에 대해 알아보자.

Arrays.sort()

→ 듀얼피봇퀵소트 (2개의 피봇으로 3개의 구간으로 나누어서 퀵정렬을 하는 방식)

퀵소트가 O(NlogN)의 시간 복잡도를 가지지만, CPU, 메모리 구조상 이득 + 평균 연산량을 줄여냄

L은 왼쪽 끝, G는 오른쪽 끝에 시작, K는 L에서 시작해 G까지 옮겨가며 원소가 속하는 구간이 어디인지 찾아 swap. ?의 부분은 파티셔닝이 끝나면 사라지고, 나누어진 구간에 대해서 다시 재귀적으로 실행하게 된다.

과정 설명이 잘 되어있다. → https://gwpark.tistory.com/1743

Collections.sort()

→ TimSort (삽입 정렬과 합병 정렬을 결합해서 만듬, Java 7부터)

Merge Sort를 이용해서 큰 Array를 여러 크기로 나누고, Insertion Sort로 작은 조각을 정렬한다.

거기에 더불어 Insertion Sort는 Binary Insertion Sort를 사용한다. (분류된 값에서 들어갈 곳을 찾을 때 이진 탐색을 사용)

둘의 알고리즘이 다른 이유

두 자료구조가 다른 알고리즘을 사용하는 이유는 바로 참조 지역성의 원리 때문이다.

어떤 알고리즘을 이용해서 Sorting을 할 때 실제 동작시간은 $C×nlogn+α$ 가 된다.

그리고 여기서 C는 참조 지역성 원리를 얼마나 잘 만족하는가에 있다.

Array의 경우는 모든 원소들이 모여 있기 때문에 C의 값이 작게 된다. 그렇기 때문에 상대적으로 원소 간의 참조 이동이 많은 QuickSort를 사용하더라도 큰 무리가 가지 않는다.

하지만, Collection의 경우는 ArrayList도 존재하지만 접근할 요소의 위치가 산발적인 LinkedList가 같이 존재한다. 따라서 참조 인접성이 좋지 않아 C의 값이 높게 된다.

이런 상황에서는 참조인접성을 조금이라도 줄일 수 있도록 하는 TimSort를 선택하는 것이 조금 더 바람직하다.

참조 글

https://d2.naver.com/helloworld/0315536 → TimSort에 관하여