Java의 Arrays.sort는 듀얼피봇 퀵정렬(Dual-Pivot QuickSort)을 사용한다. 듀얼 피봇 퀵정렬은 피봇을 2개를 두고 3개의 구간을 만들어 퀵정렬을 진행한다는 것이다. 이 방식은 하나의 피봇으로 진행하는 퀵 정렬에 비해 좋은 성능을 낸다고 알려진다. 그 이유는 퀵 정렬의 경우 최악의 경우의 피봇을 잡았을 때 (오름차순에서 가장 작은 수 or 내림차순에서 가장 높은 수) 버블정렬과 같은 시간 복잡도가 나온다. 때문에 평균은 O(nlog₂n)로 준수한 시간 복잡도를 갖지만 최악의 경우 O(n²)가 나온다. 때문에 두개의 피봇을 두고 퀵 정렬을 한다. 그렇기에 그 기본이 되는 퀵 정렬에 대해 공부해 보았다. 퀵정렬의 정렬 방식 피벗을 기준으로 피벗보다 작은 요소들은 피벗의 왼쪽에 위치시..
