PDQ Sort (현재 가장 빠른 정렬 알고리즘)

소스코드: https://github.com/orlp/pdqsort

논문: https://arxiv.org/abs/2106.05123

Best        Average     Worst       Memory      Stable      Deterministic
n           n log n     n log n     log n       No          Yes

 

 

PDQSort 요약

 

pdq sort는 Pattern-Defeating Quicksort입니다.

특정한 패턴이 감지되는 경우에 빠르게 소팅할 수 있다는 특징이 있으며,

3가지 기본적인 소팅을 합친 하이브리드 소팅입니다.

rust에서는 기본 sorting으로 채택했으며, 대략 45% 정도의 성능 향상이 있다고 합니다(링크).

 

아이템들이 정렬된 경우에 O(n)의 시간이 걸리고(이 과정에서 insertion sort가 사용될 수 있음)

일반적인 경우는 random pivot을 선택해서 quicksort로 정렬하고 (O(n log n))

random pivot이 잘 못 선택되어 최악이라고 판단되는 경우에는 heap sort로 전환해서 (O(n log n))

정렬을 수행합니다.

 

단점으로는 unstable sort이기 때문에 같은 키값을 가진 요소들이 섞일 수 있습니다.

 

---

 

The Best Case - O(n)

몇 가지 경우들에서 선형으로 정렬이 수행됩니다.1. 엄격하게 오름차순 정렬된 경우2. 엄격하게 내림차순 정렬된 경우3. 동일한 요소만 포함하는 경우4. 엄격하게 오름차순 정렬 되어 있으나 맨 마지막 요소만 정렬되지 않은 경우

 

 

- Best Case들의 경우

선형시간으로 정렬을 하기 위해서 quicksort의 파티셔닝을 한 번 했을 때, 요소들의 교환이 이루어지지 않았다면 insertion sort로 다음 파티션을 정렬합니다. 

insertion sort의 시간복잡도는 O(n)이기 때문에 O(n)만에 정렬될 수 있습니다.

insertion sort는 상수 개의 요소들이 정렬이 필요하다고 판단되면, 종료됩니다.

 

- 동일한 요소만 포함하는 경우

이 경우는 별도로 판단합니다.

---

 

The Average Case - O(n log n)

- 평균적으로 패턴이 감지되지 않는 데이터의 경우

   pdqsort는 중앙값 3의 피벗 선택을 사용하는 퀵 정렬(재귀호출)

- 정렬할 요소의 수가 적으면 삽입 정렬로 전환합니다

 

 

pdqsort는 큰 배열(1000개 이상의 요소)을 정렬할 때 퀵소트를 구현하는 기존 방식에 비해 속도가 크게 향상되었음

"BlockQuicksort: Branch Mispredictions가 Quicksort에 영향을 미치지 않는 방법"

에 설명된 새로운 기술 때문입니다.

 

L1 캐시에 값을 넣어서 분기 예측기를 우회하는 방법입니다.

buffer_num = 0; buffer_max_size = 64;
for (int i = 0; i < buffer_max_size; ++i) {
    // With branch:
    if (elements[i] < pivot) { buffer[buffer_num] = i; buffer_num++; }
    // Without:
    buffer[buffer_num] = i; buffer_num += (elements[i] < pivot);
}

하지만 이 방법은 비교 연산자가 분기를 하지 않는 경우에만 속도향상이 있습니다.

 

아래의 조건을 동시에 만족하면 분기를 하지 않습니다.

1) C++11 이상을 사용

2) int 등 산술 가능한 타입을 사용

3) std::less 또는 std::greater 같은 C++의 비교 연산자를 사용

branchless partitioning을 사용하려면 pdqsort 대신 pdqsort_branchless를 호출할 수도 있습니다.

 

---

 

The Worst Case - O(n log n)

랜덤 피벗을 선택하는 방법으로 퀵소트가 최악인 경우를 벗어납니다.

하지만, 너무 재귀의 깊이가 깊어지면 O(n log n) 인 힙소트로 전환합니다.

나쁜 파티션이 너무 많으면, heap sort로 정렬하는 방식으로 전환합니다.

 

Bad Partitions

분할 후 피벗 위치가 12.5%(1/8) 백분위수 미만 또는 87.5% 백분위수 이상인 경우 잘못된 분할이 발생합니다.

즉, 분할이 매우 불균형한 상태입니다.

이런 경우에 파티션을 4부분으로 나눠서 각 위치를 섞습니다.

 

log(n) 개 이상의 잘못된 파티션이 나오면, 힙 정렬로 변경합니다.

 

 

---

최근 rust와 golang에서 unstable sort임에도 불구하고 빠르기 때문에 pdq 소트로 채택된 것으로 보입니다.

golang에서는 1.19 버전부터 사용되고,

rust에서는 1.20.0 버전부터 사용됩니다.