~/blog/sorting-in-the-wild/ko.mdx

sort()를 부르면 실제로 도는 것: C++, Rust, Go의 퀵소트

교과서의 퀵소트는 이미 정렬된 배열에서 O(n²)이 됩니다. 그래서 C++, Rust, Go의 표준 라이브러리는 아무도 교과서 퀵소트를 쓰지 않습니다. libstdc++의 introsort, Rust와 Go 1.19의 pdqsort, 그리고 세 언어의 안정 정렬이 각각 어떤 입력을 어떻게 막는지 움직이는 그림으로 따라가 봤습니다.

지난달 Go 1.19가 나오면서 sort.Sort의 알고리즘이 pdqsort로 바뀌었습니다.1 릴리스 노트에는 “몇몇 흔한 경우에 더 빠르다”는 한 줄뿐이라, 무엇이 왜 빨라졌는지 알려면 코드를 열어 봐야 했습니다. 연 김에 Rust와 C++ 쪽도 같이 봤습니다. 셋 다 이름은 sort이고 셋 다 퀵소트에서 출발했지만, 퀵소트의 약점을 막는 방법은 꽤 다릅니다.

이 글의 그림은 모두 직접 움직여 볼 수 있습니다. 막대 하나가 원소 하나이고 높이가 값입니다. 노란색은 지금 비교하는 두 원소, 빨간색은 방금 자리를 바꾼 원소, 테두리만 있는 막대는 피벗입니다. 지금 다루는 구간 밖은 흐리게 그립니다. 여러 칸이 나란히 있으면 같은 입력을 놓고 경주를 합니다. 한 프레임마다 모든 칸이 비교나 교환을 똑같은 수만큼 하니, 일을 덜 하는 쪽이 먼저 끝납니다.

그림과 표의 비교 횟수는 세 라이브러리의 정렬을 JavaScript로 옮긴 코드에서 셌습니다. 원본의 분기와 상수를 그대로 따랐고, 입력은 시드 7로 만든 같은 배열입니다. 실제 라이브러리의 시간을 잰 것이 아니니 절댓값보다는 서로의 비율로 읽어 주세요.

삽입 정렬부터

정렬을 처음 배우면 대개 삽입 정렬부터 봅니다. 왼쪽부터 한 장씩 집어 이미 정리된 카드 사이에 끼워 넣는 방식입니다. 한 번 끼울 때마다 앞의 카드들과 하나씩 비교하니, 무작위 입력에서는 비교가 대략 n2/4n^2/4번입니다.

퀵소트는 피벗 하나를 골라 그보다 작은 것은 왼쪽, 큰 것은 오른쪽으로 보냅니다. 그러면 피벗은 제자리를 찾고, 양쪽을 따로 정렬하면 끝납니다. 피벗이 매번 가운데쯤에 떨어지면 반씩 줄어드니 비교는 nlog⁡2nn \log_2 n 정도가 됩니다.

같은 무작위 입력 60개. 오른쪽 퀵소트가 끝났을 때 왼쪽 삽입 정렬은 아직 3분의 1쯤 와 있습니다.

60개에서는 비교 횟수가 922번과 430번으로 두 배 남짓 차이지만, 원소가 늘면 격차가 빠르게 벌어집니다. 200개짜리 무작위 배열에서 삽입 정렬은 10,054번, 퀵소트는 1,764번 비교했습니다.

그런데 아래에서 볼 세 라이브러리는 모두 삽입 정렬을 버리지 않았습니다. 퀵소트로 쪼개다가 구간이 십수 개로 작아지면 삽입 정렬로 넘깁니다. 원소가 적으면 n2n^2과 nlog⁡nn \log n의 차이보다 재귀 호출과 피벗 선택에 드는 고정 비용이 더 크고, 삽입 정렬은 메모리를 앞에서 뒤로 순서대로 훑어서 캐시에도 잘 맞기 때문입니다. 그 경계가 C++은 16, Rust는 20, Go는 12입니다.

같은 퀵소트, 다른 분할

퀵소트는 분할(partition)을 어떻게 하느냐에 따라 성격이 꽤 달라집니다. 교과서에 자주 나오는 두 가지가 Lomuto와 Hoare 방식입니다.

Lomuto 분할은 마지막 원소를 피벗으로 잡고, 앞에서부터 훑으며 피벗보다 작은 원소를 왼쪽 경계로 하나씩 옮깁니다. 코드가 짧아서 교재에 많이 실립니다. Hoare 분할은 양 끝에서 포인터 두 개가 안쪽으로 걸어오다가, 왼쪽은 피벗보다 크거나 같은 원소에서, 오른쪽은 작거나 같은 원소에서 멈추고 둘을 바꿉니다. 아래 그림에서 입력을 바꿔 가며 보면 차이가 잘 보입니다.

입력 메뉴에서 '정렬됨'을 골라 보세요. Lomuto는 한 칸씩만 줄어듭니다.

무작위 입력에서는 둘 다 무난합니다. n=200에서 Lomuto가 1,878번, Hoare가 2,300번 비교했고 교환은 Lomuto가 740번, Hoare가 354번이었습니다. Hoare는 비교를 조금 더 하는 대신 교환을 절반 이하로 합니다.

정렬된 입력에서 Lomuto는 무너집니다. 마지막 원소가 늘 최댓값이니 분할할 때마다 피벗 하나만 떨어져 나가고, 나머지 n−1n-1개가 그대로 다음 단계로 넘어갑니다. 비교는 n(n−1)/2n(n-1)/2, n=200에서 정확히 19,900번이고 재귀 깊이는 199입니다. 이미 정렬된 배열을 다시 정렬하는 일은 실무에서 생각보다 흔합니다. 로그를 시간순으로 쌓아 두었다가 정렬하거나, 정렬된 목록 끝에 몇 개를 붙이고 다시 정렬하는 경우가 그렇습니다.

퀴즈기울어진 분할을 확인합니다

답을 고르면 해설이 나옵니다.

1문제 중 0개 맞힘

  1. 마지막 원소를 피벗으로 쓰는 Lomuto 퀵소트에 이미 정렬된 배열을 넘깁니다. 비교가 제곱으로 늘어나는 이유는 무엇입니까?

‘값 4종’도 눈여겨볼 만합니다. 같은 값이 많으면 Lomuto는 피벗과 같은 원소를 모두 한쪽으로 몰아서 다시 한쪽으로 기웁니다(5,446번, 깊이 53). Hoare는 같은 값에서도 멈추고 바꾸기 때문에 같은 값이 양쪽으로 고르게 나뉩니다(1,943번). 쓸데없어 보이는 교환이 균형을 지켜 주는 셈입니다.

Hoare도 약점이 있습니다. 이 구현은 가운데 원소를 피벗으로 쓰는데, 값이 가운데로 갈수록 커졌다가 다시 작아지는 산 모양 입력에서는 가운데가 늘 최댓값입니다. 그래서 10,900번 비교하고 깊이는 104까지 갑니다. 피벗을 한 자리에서만 뽑으면 그 자리를 노리는 입력이 반드시 있습니다.

피벗을 세 개 중에서 고르기

흔한 처방은 여러 자리에서 후보를 뽑아 그 중앙값을 피벗으로 쓰는 것입니다. 처음, 가운데, 끝에서 하나씩 뽑아 가운데 값을 쓰면 median-of-3, 이것을 세 번 해서 다시 중앙값을 고르면 ninther(아홉 개 중 하나)입니다. 정렬된 입력에서는 가운데 값이 진짜 중앙값이니 최적의 피벗이 나옵니다. 산 모양에서도 양 끝이 작고 가운데가 크니 셋 중 중앙값은 적당한 값이 됩니다.

n=200에서 median-of-3 퀵소트는 정렬된 입력을 1,529번, 산 모양을 2,521번 비교로 끝냈습니다. 깊이도 각각 5와 11입니다. 흔한 입력은 이것으로 대부분 막힙니다. 문제는 일부러 만든 입력입니다.

퀵소트를 죽이는 입력

1999년 Doug McIlroy가 “A Killer Adversary for Quicksort”라는 짧은 논문을 냈습니다.2 아이디어가 재미있습니다. 정렬 함수에 넘기는 비교 함수를 조작해서, 정렬이 진행되는 동안 입력을 만들어 냅니다.

처음에는 모든 원소의 값이 정해져 있지 않습니다. 논문에서는 이 상태를 기체(gas)라고 부릅니다. 비교 함수가 기체 둘을 비교하라는 요청을 받으면, 그중 하나를 지금까지 정해진 어떤 값보다도 큰 값으로 얼립니다. 어느 쪽을 얼릴지는 피벗 후보로 보이는 쪽, 즉 비교에 많이 불려 나온 쪽을 고릅니다. 그러면 퀵소트가 고른 피벗은 늘 남은 원소 중 가장 작은 쪽에 가깝게 됩니다. 정렬이 끝나면 모든 원소가 얼어 있고, 그 값들을 그대로 배열로 만들면 이 퀵소트 전용의 최악 입력이 됩니다.

조건은 퀵소트가 결정적이어야 한다는 것 하나뿐입니다. 피벗을 고르는 규칙이 얼마나 정교하든, 같은 입력에 같은 순서로 비교한다면 이 방법으로 무너뜨릴 수 있습니다.

median-of-3 퀵소트를 겨냥해 만든 64개짜리 킬러 입력. 왼쪽은 한 번에 두 개씩만 줄어들고, 가운데 introsort는 깊이 한도에 걸리면 heapsort로 넘어갑니다.

왼쪽 칸을 보면 분할이 끝날 때마다 구간이 두 칸씩만 줄어듭니다. 64개에서는 1,142번 비교, 깊이 25로 끝나 그리 극적이지 않지만, 크기를 키우면 이야기가 다릅니다.

n무작위 입력킬러 입력배율최대 깊이
1,00012,521253,39420배493
10,000160,40225,034,894156배4,993

10,000개에서 비교가 2,500만 번이고 재귀 깊이가 거의 5,000입니다. 이 정도면 느린 것보다 스택이 먼저 걱정입니다. 웹 서버가 사용자가 보낸 목록을 정렬한다면, 그 목록을 조작해 CPU를 붙잡아 둘 수 있다는 뜻이기도 합니다.

해결책은 두 갈래입니다. 피벗을 무작위로 골라 공격자가 순서를 예측하지 못하게 하거나, 무너지는 것을 감지해 다른 알고리즘으로 갈아타는 것입니다. 세 언어는 모두 두 번째를 골랐습니다. 무작위 피벗은 기대값으로만 빠르고 최악이 여전히 O(n2)O(n^2)이며, 같은 입력의 실행 시간이 매번 달라지는 것도 라이브러리로서는 반갑지 않습니다.

C++: introsort

libstdc++의 std::sort는 1997년 David Musser가 제안한 introsort입니다.3 퀵소트로 시작하되 재귀 깊이에 한도를 둡니다. 정상적인 퀵소트라면 깊이가 log⁡2n\log_2 n 근처에서 끝나야 하니, 그보다 한참 깊어지면 피벗 선택이 실패하고 있다는 신호입니다. 그때 그 구간을 heapsort로 정렬합니다.

heapsort는 어떤 입력에서도 O(nlog⁡n)O(n \log n)이지만 평소에는 퀵소트보다 느립니다. n=200 무작위 입력에서 heapsort는 2,461번, median-of-3 퀵소트는 1,764번 비교했습니다. 비교 횟수보다 더 큰 문제는 메모리 접근입니다. 힙은 인덱스 ii의 자식이 2i+12i+1, 2i+22i+2에 있어서 아래로 내려갈수록 멀리 떨어진 곳을 건드립니다.

heapsort(오른쪽)는 먼저 힙을 만들고, 최댓값을 하나씩 맨 뒤로 보냅니다. 막대가 배열 전체를 크게 오가는 것이 보입니다.

introsort는 둘의 장점만 씁니다. 평소에는 퀵소트이고, 최악의 경우에만 heapsort가 됩니다. 중심이 되는 루프는 짧습니다.

bits/stl_algo.h (libstdc++, 요약)
template<typename _Iter, typename _Size, typename _Compare>
void __introsort_loop(_Iter __first, _Iter __last,
_Size __depth_limit, _Compare __comp)
{
while (__last - __first > int(_S_threshold)) // 16
{
if (__depth_limit == 0)
{
std::__partial_sort(__first, __last, __last, __comp);
return;
}
--__depth_limit;
_Iter __cut =
std::__unguarded_partition_pivot(__first, __last, __comp);
std::__introsort_loop(__cut, __last, __depth_limit, __comp);
__last = __cut;
}
}

구간이 16개 이하로 줄면 여기서는 아무것도 하지 않고 돌아갑니다. 작은 구간들은 정렬되지 않은 채로 남지만, 각 구간의 값은 이미 제 구간 안에 들어와 있습니다.

깊이 한도를 다 쓰면 남은 구간 전체를 __partial_sort로 정렬합니다. 가운데 인자가 __last이니 구간 전부를 정렬하라는 뜻이고, 이 함수의 실체는 heapsort입니다. 한도는 std::sort가 2⌊log⁡2n⌋2\lfloor\log_2 n\rfloor로 넘깁니다.

피벗은 __move_median_to_first가 고릅니다. 두 번째, 가운데, 마지막에서 한 칸 앞 원소 중 중앙값을 맨 앞으로 옮깁니다. 그다음 Hoare 방식으로 분할하는데, 양쪽 끝에 피벗보다 작지 않은 값과 크지 않은 값이 있다는 것을 알기 때문에 포인터가 배열 밖으로 나가는지 검사하지 않습니다(unguarded).

오른쪽은 재귀로, 왼쪽은 while 루프로 처리합니다. 꼬리 재귀를 손으로 루프로 바꾼 것입니다.

__introsort_loop가 끝나면 std::sort는 __final_insertion_sort로 배열 전체를 삽입 정렬 한 번에 마무리합니다. 원소마다 제 구간 안에서만 움직이면 되니, 16개짜리 구간을 따로따로 정렬하는 것과 비교 횟수는 비슷하고 함수 호출은 한 번이면 됩니다.

효과는 킬러 입력에서 바로 보입니다. 같은 median-of-3 피벗을 쓰는데, 깊이 한도 하나로 2,500만 번이 50만 번이 됩니다.

n = 10,000무작위정렬됨킬러최대 깊이(킬러)
median-of-3 퀵소트160,402166,67725,034,8944,993
introsort (std::sort)160,402166,677500,91927
heapsort235,624244,460233,001

킬러 입력에서도 introsort가 heapsort보다 두 배 넘게 비교합니다. 깊이 26까지는 계속 나쁜 분할을 하다가 그제야 heapsort로 넘어가기 때문입니다. 그래도 O(nlog⁡n)O(n \log n) 안에 머문다는 것이 중요합니다.

한편 표의 둘째 열은 아쉬운 부분입니다. 이미 정렬된 10,000개를 정렬하는데 무작위 입력보다 비교를 더 합니다. introsort는 입력이 이미 정렬되어 있는지 알아보지 않습니다. 이 부분을 손본 것이 pdqsort입니다.

Rust와 Go: pdqsort

pdqsort(pattern-defeating quicksort)는 Orson Peters가 2015년에 공개하고 2021년에 논문으로 정리한 알고리즘입니다.4 뼈대는 introsort와 같습니다. 퀵소트로 쪼개고, 작은 구간은 삽입 정렬, 깊이 한도를 넘으면 heapsort. 여기에 입력의 패턴을 알아보고 이용하는 장치가 몇 개 붙어 있습니다. Rust는 2017년부터 slice::sort_unstable에 이 알고리즘을 썼고, Go는 1.19에서 sort.Sort와 sort.Slice를 이것으로 바꿨습니다.

예 아니오 예 아니오 예, 직전 분할도 고르면 성공 실패 아니오 예 아니오 예 아니오 구간 v 길이 ≤ 20?(Go는 12) 삽입 정렬 한도 소진? heapsort 피벗 고르기3개, 50개 이상이면 9개 후보들이 이미순서대로였나? 부분 삽입 정렬 시도어긋난 곳 5개까지 끝 E 같은 값을 한쪽에 몰고그 구간은 건너뜀 분할 작은 쪽이길이/8 미만? 몇 개를 섞고한도 1 감소 양쪽 재귀

하나씩 보겠습니다.

피벗 후보가 이미 정렬된 순서인지 봅니다. 피벗을 고르려고 후보 셋(또는 아홉)을 비교하는 김에, 후보끼리 자리를 바꿀 일이 한 번도 없었는지 셉니다. 한 번도 없었다면 이 구간 전체가 이미 정렬되어 있을 가능성이 높습니다. 직전 분할도 고르게 나뉘었고 그때 원소를 하나도 옮기지 않았다면, 퀵소트를 돌리기 전에 삽입 정렬을 시도합니다. 단, 어긋난 원소를 다섯 개까지만 고치고 그 이상이면 포기합니다. 손해가 나도 O(n)O(n)을 넘지 않도록 한 것입니다. 거꾸로 후보끼리 자리를 바꾼 횟수가 최대치(12번)에 이르면 구간이 거꾸로 정렬되어 있다고 보고 통째로 뒤집습니다.

그래서 정렬된 입력과 역순 입력이 거의 nn번 비교로 끝납니다. 10,000개에서 둘 다 10,011번이었습니다. introsort의 166,677번, 122,044번과 비교하면 열 배 이상 차이입니다.

같은 값이 많으면 한 번에 치웁니다. 분할한 오른쪽 구간을 다시 정렬할 때, 이번 피벗이 구간 바로 왼쪽의 값(이전 피벗)과 같다면 이 구간에는 그 값보다 작은 원소가 없다는 뜻입니다. 이때는 이전 피벗과 같은 값을 모두 왼쪽에 모으고 그 부분을 다시 보지 않습니다. 값의 종류가 kk개면 이런 분할이 kk번 정도 일어나고 끝납니다.

분할이 기울면 패턴을 깹니다. 작은 쪽이 전체의 1/8도 안 되면 구간 가운데 근처의 원소 몇 개를 의사 난수로 고른 자리와 바꾸고 한도를 하나 줄입니다. 공격자가 노린 배치를 흐트러뜨리는 장치입니다. 한도는 nn의 비트 수, 10,000이면 14입니다. 이 횟수만큼 나쁜 분할이 쌓이면 introsort처럼 heapsort로 넘어갑니다.

입력을 바꿔 가며 보세요. 정렬됨과 역순은 한 번 훑고 끝납니다. 값 4종에서는 '같은 값 묶기'가 몇 번 나오고 끝납니다.

Rust와 Go의 pdqsort는 같은 설계이지만 분할 방식이 다릅니다. Rust는 Edelkamp와 Weiß의 BlockQuicksort 분할을 씁니다.5 피벗과의 비교 결과를 먼저 작은 버퍼(블록)에 몰아서 기록하고, 교환은 나중에 한꺼번에 합니다. 비교 결과에 따라 분기하지 않으니 CPU의 분기 예측이 틀릴 일이 줄어듭니다. 무작위 데이터에서 분할 루프의 분기는 반반 확률이라 예측기가 거의 맞히지 못하는데, 그 비용을 없애는 것입니다. Rust의 블록은 원소 128개인데, 위 그림에서는 움직임이 보이도록 8개로 줄였습니다. Go는 sort.Interface가 Less와 Swap만 제공하기 때문에 원소를 버퍼에 담을 수 없고, 평범한 Hoare 분할을 씁니다. 삽입 정렬로 넘기는 크기도 Go가 12로 Rust의 20보다 작습니다.

introsort, Go의 pdqsort, Rust의 pdqsort. 처음 입력은 값 4종입니다.

n=10,000에서 세 구현의 비교 횟수입니다.

입력introsort (C++)pdqsort (Go)pdqsort (Rust)
무작위160,402144,680154,658
정렬됨166,67710,01110,011
역순122,04410,01110,011
값 4종113,28932,58332,591
산 모양358,390130,613138,454
킬러 (median-of-3용)500,91992,83796,438

무작위 입력에서는 세 구현의 차이가 10% 안쪽입니다. 비교 횟수만 보면 Rust가 Go보다 약간 많은데, 블록 분할은 비교를 줄이려는 것이 아니라 분기 예측 실패를 줄이려는 것이라 이 표로는 장점이 드러나지 않습니다. 차이는 패턴이 있는 입력에서 납니다.

마지막 줄의 킬러 입력은 median-of-3 퀵소트를 겨냥해 만든 것이라 pdqsort에는 그다지 위협이 되지 않습니다. 그래서 pdqsort 자신을 겨냥해서도 만들어 봤습니다. 1,000개에서 7,157번 비교, 깊이 3으로 무작위 입력(11,486번)보다 오히려 적게 끝났습니다. 이 글의 공격 코드가 피벗 선택과 패턴 깨기를 함께 따라가지 못한 것으로 보입니다. 그렇다고 pdqsort를 무너뜨릴 수 없다는 뜻은 아닙니다. pdqsort도 결정적이니 더 정교하게 만든 공격이라면 한도를 다 쓰게 만들 수 있을 것입니다. 그때도 heapsort가 받쳐 주니 O(nlog⁡n)O(n \log n)은 지켜집니다.

Go 1.18까지의 sort.Sort도 퀵소트였습니다. 40개가 넘으면 ninther로 피벗을 고르고, 깊이가 2⌈log⁡2(n+1)⌉2\lceil\log_2(n+1)\rceil을 넘으면 heapsort로 넘어가고, 12개 미만은 삽입 정렬로 마무리했습니다. 사실상 introsort입니다. 1.19의 변경은 여기에 정렬된 입력 감지, 같은 값 처리, 패턴 깨기를 더한 것이고, 릴리스 노트의 “몇몇 흔한 경우”가 바로 위 표에서 차이가 큰 줄들입니다.

안정 정렬은 따로 있습니다

지금까지 본 알고리즘은 모두 불안정 정렬입니다. 같은 값을 가진 원소의 원래 순서가 바뀔 수 있습니다. 이름순으로 정렬된 직원 목록을 부서로 다시 정렬했을 때 같은 부서 안에서 이름순이 유지되기를 바란다면 안정 정렬이 필요합니다. 세 언어 모두 안정 정렬은 퀵소트가 아니라 병합 정렬 계열입니다. 그리고 여기서는 세 언어가 정말로 제각각입니다.

C++의 std::stable_sort는 배열 크기의 절반만큼 임시 버퍼를 빌려 바닥부터 올라가는 병합 정렬을 합니다. 먼저 7개씩 끊어 삽입 정렬하고, 14개, 28개, 56개 순으로 이웃한 덩어리를 병합합니다. 병합할 때마다 배열과 버퍼 사이를 오가며 원소를 씁니다. 입력에 이미 정렬된 구간이 있는지는 보지 않습니다. 버퍼를 얻지 못하면 회전을 이용한 제자리 병합으로 떨어지는데, 그쪽은 O(nlog⁡2n)O(n \log^2 n)입니다.

Rust의 slice::sort는 TimSort를 단순하게 만든 것입니다. 뒤에서부터 이미 정렬된 구간(run)을 찾고, 거꾸로 정렬된 구간은 뒤집고, 10개보다 짧은 run은 삽입 정렬로 늘립니다. run을 스택에 쌓으며 TimSort와 같은 길이 규칙으로 병합합니다. Python이나 Java의 TimSort와 달리 galloping(한쪽에서 연속으로 이길 때 이진 탐색으로 건너뛰기)은 없습니다. 버퍼는 배열의 절반입니다.

Go의 sort.Stable은 버퍼를 쓰지 않습니다. 정확히는 쓸 수 없습니다. sort.Interface로는 원소를 꺼내 다른 곳에 저장할 방법이 없고, 할 수 있는 것은 두 자리를 비교하고 바꾸는 것뿐입니다. 그래서 20개씩 삽입 정렬한 다음, Kim과 Kutzner의 SymMerge로 제자리 병합합니다.6 두 덩어리를 대칭으로 이진 탐색해 자를 자리를 찾고, 가운데 부분을 회전(rotation)해 맞바꾼 다음 양쪽을 재귀로 병합합니다. 회전은 교환으로만 이루어지니 교환이 많아집니다.

아래에서는 같은 키를 가진 원소에 서로 다른 입력 번호를 붙였습니다. 키 1의 원래 순서는 2, 4, 6입니다. 불안정한 Lomuto 퀵소트는 이 순서를 뒤집지만, 안정 정렬은 보존합니다.

입력 순서

  1. 2#1
  2. 1#2
  3. 2#3
  4. 1#4
  5. 2#5
  6. 1#6

불안정 · Lomuto 퀵소트

  1. 1#6
  2. 1#4
  3. 1#2
  4. 2#1
  5. 2#3
  6. 2#5

안정 · Rust 병합 정렬

  1. 1#2
  2. 1#4
  3. 1#6
  4. 2#1
  5. 2#3
  6. 2#5
큰 숫자는 정렬 키, 작은 숫자는 입력에서의 위치입니다.
C++ stable_sort, Rust sort, Go sort.Stable. 막대가 한 칸씩 옮겨지는 것은 버퍼에서 되돌려 쓰는 것이고, Go 쪽의 긴 교환 줄은 회전입니다.

n=1,000에서 센 값입니다. ‘쓰기’는 버퍼와 배열 사이에서 원소를 옮긴 횟수입니다.

입력C++ 비교C++ 쓰기Rust 비교Rust 쓰기Go 비교Go 교환
무작위9,5787,6829,7736,88012,41519,730
정렬됨5,1067,68299901,2290
역순6,4307,68299909,84213,832
산 모양5,8567,6821,9981,0007,2209,594

C++의 쓰기 횟수가 입력과 상관없이 7,682로 같은 것이 눈에 띕니다. 덩어리 크기가 미리 정해져 있어서 병합 횟수도 정해져 있기 때문입니다. Rust는 run을 찾으니 정렬된 입력과 역순 입력은 999번 비교, 즉 한 번 훑고 끝납니다(역순은 뒤집는 데 교환 500번이 더 듭니다). 산 모양은 올라가는 run 하나와 내려가는 run 하나라서 뒤집고 한 번 병합하면 됩니다. Go는 메모리를 하나도 쓰지 않는 대신 무작위 입력에서 교환이 2만 번에 가깝습니다.

어느 쪽이 낫다고 하기는 어렵습니다. Go가 안정 정렬에 버퍼를 쓰지 않는 것은 인터페이스 설계에서 나온 결과이고, 그 덕에 어떤 컨테이너든 Len, Less, Swap만 구현하면 정렬할 수 있습니다. 대신 원소를 직접 다룰 수 있는 언어에서 기대할 만한 성능은 포기한 셈입니다.

한눈에 보기

C++ (libstdc++)RustGo 1.19
불안정 정렬std::sort: introsortsort_unstable: pdqsort, 블록 분할sort.Sort: pdqsort
삽입 정렬로 넘기는 크기162012
깊이 한도2⌊log⁡2n⌋2\lfloor\log_2 n\rfloornn의 비트 수nn의 비트 수
정렬된 입력 감지없음있음있음
안정 정렬std::stable_sort: 7개 단위 병합, 버퍼 n/2n/2sort: TimSort식 run 병합, 버퍼 n/2n/2sort.Stable: 20개 단위 + SymMerge, 버퍼 없음
"median-of-3" "introsort" "heapsort" "C++ stable" "Go Stable" "pdqsort" "Rust sort" 0 50000 100000 150000 200000 250000 비교 횟수 이미 정렬된 10,000개를 정렬할 때 비교 횟수 (낮을수록 좋음)

정리

  • 세 언어 모두 표준 정렬은 퀵소트, 삽입 정렬, heapsort의 조합입니다. 퀵소트가 나쁜 피벗을 계속 고르면 깊이 한도에 걸려 heapsort로 넘어가니, 최악의 경우도 O(nlog⁡n)O(n \log n)입니다.
  • 결정적인 퀵소트는 McIlroy의 방법으로 최악의 입력을 만들 수 있습니다. median-of-3 퀵소트는 10,000개에서 무작위 입력의 156배를 비교했고, 같은 피벗 규칙에 깊이 한도만 더한 introsort는 3배에 그쳤습니다.
  • C++의 std::sort는 입력이 이미 정렬되어 있는지 보지 않습니다. Rust와 Go 1.19의 pdqsort는 정렬된 입력, 역순 입력, 같은 값이 많은 입력을 알아보고 거의 선형 시간에 끝냅니다.
  • 안정 정렬은 세 언어가 모두 병합 정렬 계열이지만 버퍼 사용이 다릅니다. C++과 Rust는 절반 크기 버퍼를 쓰고, Go는 sort.Interface의 제약 때문에 버퍼 없이 회전으로 병합합니다.

sort() 한 줄 뒤에는 이렇게 입력의 모양을 살피는 코드가 꽤 많이 들어 있습니다. 평소에는 몰라도 되지만, 이미 정렬된 데이터를 반복해서 정렬하고 있거나, 외부에서 들어온 데이터를 정렬하고 있거나, 같은 값이 잔뜩 있는 배열을 정렬하고 있다면 어떤 언어의 어떤 함수를 부르는지에 따라 몇 배씩 차이가 날 수 있습니다.

퀴즈정렬 함수를 고른다면

답을 고르면 해설이 나옵니다.

3문제 중 0개 맞힘

  1. pdqsort의 피벗 후보가 이미 순서대로입니다. 이 신호만 보고 구간 전체가 정렬됐다고 처리해도 됩니까?

  2. 이름순 직원 목록을 부서로 다시 정렬하면서 같은 부서 안의 이름순을 보존하려고 합니다. 무엇을 선택해야 합니까?

  3. 본문의 비교 횟수 표에서 Rust의 블록 분할이 Go보다 조금 더 비교합니다. 이것만으로 Rust 쪽 실행 시간이 더 길다고 판단할 수 있습니까?

각주

  1. Go 1.19 릴리스 노트의 sort 항목. 구현은 src/sort/zsortinterface.go와 zsortfunc.go에 있고, 둘 다 gen_sort_variants.go가 생성합니다. ↩

  2. M. Douglas McIlroy, “A Killer Adversary for Quicksort”, Software: Practice and Experience 29(4), 1999. ↩

  3. David R. Musser, “Introspective Sorting and Selection Algorithms”, Software: Practice and Experience 27(8), 1997. ↩

  4. Orson R. L. Peters, “Pattern-defeating Quicksort”, arXiv:2106.05123, 2021. Rust 구현은 library/core/src/slice/sort.rs에 있습니다. ↩

  5. Stefan Edelkamp, Armin Weiß, “BlockQuicksort: Avoiding Branch Mispredictions in Quicksort”, ESA 2016. ↩

  6. Pok-Son Kim, Arne Kutzner, “Stable Minimum Storage Merging by Symmetric Comparisons”, ESA 2004. ↩

~/blog/sorting-in-the-wild/en.mdx

What actually runs when you call sort(): quicksort in C++, Rust and Go

Textbook quicksort goes quadratic on an already sorted array, so none of the C++, Rust or Go standard libraries ship it. This post follows libstdc++'s introsort, the pdqsort in Rust and Go 1.19, and the three stable sorts, with animations showing which input each one defends against and how.

Go 1.19 came out last month, and sort.Sort switched to pdqsort along the way.1 The release notes give it one line (“faster in some common scenarios”), so finding out what got faster and why meant reading the code. While I was at it I read the Rust and C++ versions too. All three are called sort and all three start from quicksort, but they guard against quicksort’s weak spots in rather different ways.

Every figure in this post is live. Each bar is one element and its height is the value. Yellow marks the two elements being compared, red the ones just swapped, and an outlined bar is the pivot. Anything outside the range currently being worked on is dimmed. When several panels sit side by side they are racing on the same input: every panel performs the same number of compares or swaps per frame, so whichever does less work finishes first.

The compare counts in the figures and tables come from JavaScript ports of the three libraries’ sorts. The ports follow the original branches and constants, and every input is generated from the same seed (7). These are not timings of the real libraries, so read them as ratios rather than absolute numbers.

Start with insertion sort

Insertion sort is usually the first sort anyone learns. You pick up one card at a time from the left and slide it into place among the cards already in order. Each insertion compares against the cards before it one by one, so on random input it costs about n2/4n^2/4 compares.

Quicksort picks a pivot and sends everything smaller to the left and everything larger to the right. The pivot is now in its final place, and the two sides can be sorted independently. If the pivot lands near the middle every time, the problem halves at each level and you get roughly nlog⁡2nn \log_2 n compares.

The same 60 random values. When quicksort on the right is done, insertion sort on the left is about a third of the way through.

At 60 elements the counts are 922 against 430, a bit over 2×, but the gap opens quickly. On 200 random elements insertion sort made 10,054 compares and quicksort 1,764.

Yet all three libraries below still use insertion sort. Once quicksort has cut a range down to a dozen or so elements, they hand it over. With so few elements, the fixed cost of recursion and pivot selection outweighs the difference between n2n^2 and nlog⁡nn \log n, and insertion sort walks memory front to back, which caches love. The cutoff is 16 in C++, 20 in Rust and 12 in Go.

Same quicksort, different partition

How you partition changes quicksort’s character a lot. The two schemes in most textbooks are Lomuto’s and Hoare’s.

Lomuto takes the last element as the pivot and walks forward, moving every element smaller than the pivot to a growing left region. It is short, which is why textbooks like it. Hoare walks two pointers inward from both ends. The left one stops at an element greater than or equal to the pivot, the right one at an element less than or equal to it, and the two are swapped. Switching inputs in the figure below makes the difference obvious.

Pick 'sorted' from the input menu. Lomuto shrinks the range by one element at a time.

On random input both are fine. At n=200, Lomuto made 1,878 compares and Hoare 2,300, while Lomuto swapped 740 times to Hoare’s 354. Hoare compares a little more and swaps less than half as often.

On sorted input Lomuto collapses. The last element is always the maximum, so each partition peels off just the pivot and passes the other n−1n-1 elements down. That is n(n−1)/2n(n-1)/2 compares, exactly 19,900 at n=200, with a recursion depth of 199. Re-sorting an already sorted array happens more than you’d think in practice: logs accumulated in time order, or a sorted list with a few items appended and sorted again.

QuizCheckpoint: a lopsided partition

Choose an answer to see the explanation.

0 of 1 right

  1. You pass an already sorted array to Lomuto quicksort with the last element as pivot. Why does its comparison count become quadratic?

The ‘4 values’ input is worth a look too. With many duplicates, Lomuto pushes everything equal to the pivot to one side and leans again (5,446 compares, depth 53). Hoare stops and swaps on equal values as well, so duplicates end up split evenly between the two sides (1,943 compares). Swaps that look pointless are what keep it balanced.

Hoare has its own weak spot. This version uses the middle element as the pivot, and on an organ-pipe input, where values rise toward the middle and fall again, the middle is always the maximum. It takes 10,900 compares and reaches depth 104. If you always draw the pivot from one position, some input will target that position.

Choose the pivot from three

The usual remedy is to draw candidates from several positions and use their median. Take one each from the start, middle and end and use the middle value, and you have median-of-3. Do that three times and take the median of the medians, and you have the ninther. On sorted input the middle value really is the median, so the pivot is perfect. On organ-pipe input the ends are small and the middle large, so the median of the three is a reasonable value.

At n=200, median-of-3 quicksort handled sorted input in 1,529 compares and organ-pipe in 2,521, at depths 5 and 11. That blocks most ordinary inputs. The trouble is inputs built on purpose.

The input that kills quicksort

In 1999 Doug McIlroy published a short paper called “A Killer Adversary for Quicksort”.2 The idea is lovely: you rig the comparison function you pass to the sort so that it makes up the input while the sort is running.

At the start no element has a value yet. The paper calls this state gas. When the comparator is asked to compare two gas elements, it freezes one of them at a value larger than anything frozen so far. It picks the one that looks like a pivot candidate, the one that has shown up in comparisons most often. As a result, the pivot quicksort picks is always close to the smallest remaining element. When the sort finishes every element is frozen, and those values, laid out as an array, form a worst-case input for that particular quicksort.

The only requirement is that the quicksort is deterministic. However clever the pivot rule, if it compares the same input in the same order every time, this method takes it down.

A 64-element killer input built against median-of-3 quicksort. The left panel shrinks by only two elements per partition; introsort in the middle switches to heapsort when it hits its depth limit.

In the left panel the range shrinks by just two elements after each partition. At 64 elements that’s 1,142 compares and depth 25, which isn’t dramatic, but scale it up and things change.

nrandom inputkiller inputratiomax depth
1,00012,521253,39420×493
10,000160,40225,034,894156×4,993

Ten thousand elements, 25 million compares, recursion nearly 5,000 deep. At that point the stack is a bigger worry than the speed. If a web server sorts a list a user sent it, a crafted list can pin the CPU.

There are two ways out. Pick pivots at random so an attacker can’t predict the order, or detect the collapse and switch to a different algorithm. All three languages chose the second. A random pivot is only fast in expectation, the worst case is still O(n2)O(n^2), and a library whose running time varies from run to run on the same input is not something maintainers want either.

C++: introsort

libstdc++‘s std::sort is introsort, proposed by David Musser in 1997.3 It starts as quicksort but caps the recursion depth. A healthy quicksort should bottom out near log⁡2n\log_2 n, so going far deeper than that means pivot selection is failing. When that happens, the range is sorted with heapsort instead.

Heapsort is O(nlog⁡n)O(n \log n) on any input but usually slower than quicksort. On 200 random elements heapsort made 2,461 compares against median-of-3 quicksort’s 1,764. Memory access hurts more than the compare count: in a heap the children of index ii live at 2i+12i+1 and 2i+22i+2, so each step down the heap touches memory further away.

Heapsort (right) builds a heap first, then moves the maximum to the back one element at a time. Watch the bars jump across the whole array.

Introsort takes the best of both: quicksort normally, heapsort only in the worst case. Its main loop is short.

bits/stl_algo.h (libstdc++, abridged)
template<typename _Iter, typename _Size, typename _Compare>
void __introsort_loop(_Iter __first, _Iter __last,
_Size __depth_limit, _Compare __comp)
{
while (__last - __first > int(_S_threshold)) // 16
{
if (__depth_limit == 0)
{
std::__partial_sort(__first, __last, __last, __comp);
return;
}
--__depth_limit;
_Iter __cut =
std::__unguarded_partition_pivot(__first, __last, __comp);
std::__introsort_loop(__cut, __last, __depth_limit, __comp);
__last = __cut;
}
}

Once a range is down to 16 elements or fewer, the loop just returns. Those small ranges stay unsorted, but every value in them already belongs to that range.

When the depth budget runs out, the rest of the range goes to __partial_sort. The middle argument is __last, meaning “sort all of it”, and underneath this function is heapsort. std::sort passes a budget of 2⌊log⁡2n⌋2\lfloor\log_2 n\rfloor.

The pivot comes from __move_median_to_first, which moves the median of the second, middle and second-to-last elements to the front. Partitioning is Hoare-style, and because both ends are known to hold values not less than and not greater than the pivot, the pointers skip their bounds checks (unguarded).

The right side recurses; the left side is handled by the while loop. It’s tail recursion turned into a loop by hand.

After __introsort_loop returns, std::sort finishes with __final_insertion_sort, a single insertion sort over the whole array. Each element only moves within its own range, so the compare count is about the same as sorting each 16-element range separately, and it costs one call.

The payoff shows up on the killer input. Same median-of-3 pivot, and one depth limit turns 25 million compares into half a million.

n = 10,000randomsortedkillermax depth (killer)
median-of-3 quicksort160,402166,67725,034,8944,993
introsort (std::sort)160,402166,677500,91927
heapsort235,624244,460233,001

Even on the killer input introsort compares more than twice as much as plain heapsort, because it keeps making bad partitions down to depth 26 before giving up. What matters is that it stays within O(nlog⁡n)O(n \log n).

The second column is the disappointing one. Sorting 10,000 elements that are already in order costs more compares than sorting random ones. Introsort never checks whether its input is already sorted. That is what pdqsort fixes.

Rust and Go: pdqsort

pdqsort (pattern-defeating quicksort) was published by Orson Peters in 2015 and written up as a paper in 2021.4 The skeleton is introsort’s: quicksort to split, insertion sort for small ranges, heapsort past the depth limit. On top of that sit a few mechanisms that recognise patterns in the input and exploit them. Rust has used it for slice::sort_unstable since 2017, and Go switched sort.Sort and sort.Slice to it in 1.19.

yes no yes no yes, and last split was balanced success fail no yes no yes no range v len ≤ 20?(12 in Go) insertion sort budget spent? heapsort choose pivot3, or 9 if len ≥ 50 were candidatesalready in order? try partial insertion sortup to 5 fixes done E gather equal valuesand skip them partition smaller sideunder len/8? shuffle a few,budget minus 1 recurse on both

One at a time.

It checks whether the pivot candidates were already in order. While comparing the three (or nine) candidates to choose a pivot, it counts whether any of them had to be swapped. If none did, the whole range is quite likely sorted already. If the previous partition was also balanced and moved nothing, it tries insertion sort before running quicksort, but it fixes at most five misplaced elements and gives up beyond that, so a wrong guess costs no more than O(n)O(n). Conversely, if the candidates needed the maximum number of swaps (12), the range is taken to be in reverse order and is flipped in one go.

That is why sorted and reversed input both finish in about nn compares: 10,011 each at 10,000 elements, against introsort’s 166,677 and 122,044. More than a tenfold difference.

It clears out runs of equal values in one pass. When recursing into a right-hand range, if the new pivot equals the value just left of the range (the previous pivot), nothing in this range is smaller than it. In that case every element equal to the previous pivot is gathered on the left and never looked at again. With kk distinct values, this happens about kk times and the sort is done.

It breaks patterns when a split is lopsided. If the smaller side is under 1/8 of the range, a few elements near the middle are swapped with pseudo-randomly chosen positions and the budget drops by one. This scrambles whatever arrangement an attacker was aiming for. The budget is the bit length of nn, 14 for 10,000. Once that many bad splits pile up, it falls back to heapsort just like introsort.

Try different inputs. Sorted and reversed finish after one pass. With 4 values, the equal-value step fires a few times and that's it.

Rust and Go share the design but partition differently. Rust uses the BlockQuicksort partition by Edelkamp and Weiß.5 It first records the results of comparing against the pivot in a small buffer (a block) and does the swaps afterwards in bulk. Because it never branches on a comparison result, the CPU’s branch predictor has fewer chances to be wrong. On random data each partition branch is a coin flip that the predictor can barely guess, and this removes that cost. Rust’s blocks hold 128 elements; the figure uses 8 so you can see them move. Go’s sort.Interface only provides Less and Swap, so there’s no way to put elements in a buffer, and it uses a plain Hoare partition. Go also hands off to insertion sort earlier, at 12 rather than Rust’s 20.

introsort, Go's pdqsort and Rust's pdqsort. The starting input has only 4 distinct values.

Compare counts for the three at n=10,000:

inputintrosort (C++)pdqsort (Go)pdqsort (Rust)
random160,402144,680154,658
sorted166,67710,01110,011
reversed122,04410,01110,011
4 values113,28932,58332,591
organ pipe358,390130,613138,454
killer (for median-of-3)500,91992,83796,438

On random input the three are within 10% of each other. Rust makes slightly more compares than Go, but block partitioning exists to cut branch mispredictions, not compares, so this table can’t show its advantage. The differences come from inputs with structure.

The killer input in the last row was built against median-of-3 quicksort, so it barely bothers pdqsort. I built one against pdqsort itself as well. At 1,000 elements it took 7,157 compares at depth 3, fewer than random input (11,486). My adversary apparently couldn’t keep up with the pivot selection and pattern breaking together. That doesn’t mean pdqsort can’t be beaten: it is deterministic too, and a more careful attack could probably make it burn through its budget. Even then heapsort catches it, so O(nlog⁡n)O(n \log n) holds.

Go’s sort.Sort up to 1.18 was also a quicksort. It used a ninther above 40 elements, fell back to heapsort past a depth of 2⌈log⁡2(n+1)⌉2\lceil\log_2(n+1)\rceil, and finished ranges under 12 with insertion sort. Introsort in all but name. What 1.19 added was sorted-input detection, equal-value handling and pattern breaking, and the release notes’ “some common scenarios” are exactly the rows in that table with the largest gaps.

Stable sorts are a separate story

Everything so far is unstable: elements with equal keys may end up in a different order than they started. If you sort an employee list that’s already in name order by department and want names to stay in order within each department, you need a stable sort. In all three languages the stable sort is a merge sort rather than a quicksort, and here the three really do go their own ways.

C++‘s std::stable_sort borrows a temporary buffer half the size of the array and does a bottom-up merge sort. It insertion-sorts chunks of 7, then merges neighbours into 14, 28, 56 and so on, copying elements back and forth between the array and the buffer at each pass. It doesn’t look for already sorted stretches. If it can’t get a buffer it falls back to an in-place merge using rotations, which is O(nlog⁡2n)O(n \log^2 n).

Rust’s slice::sort is a simplified TimSort. It scans from the back for runs that are already sorted, reverses descending runs, and extends runs shorter than 10 with insertion sort. Runs go on a stack and are merged by TimSort’s length rules. Unlike the TimSort in Python or Java there’s no galloping (switching to binary search when one side keeps winning). The buffer is half the array.

Go’s sort.Stable uses no buffer. More precisely, it can’t. sort.Interface gives no way to take an element out and store it elsewhere; all you can do is compare two positions and swap them. So it insertion-sorts blocks of 20 and then merges in place with SymMerge by Kim and Kutzner.6 It binary-searches both halves symmetrically for the cut points, rotates the middle part to swap them, and recursively merges each side. Rotations are built from swaps, so the swap count goes up.

The figure gives equal keys distinct input positions. The original order of key 1 is 2, 4, 6. Lomuto quicksort reverses it; the stable sort preserves it.

Input order

  1. 2#1
  2. 1#2
  3. 2#3
  4. 1#4
  5. 2#5
  6. 1#6

Unstable · Lomuto quicksort

  1. 1#6
  2. 1#4
  3. 1#2
  4. 2#1
  5. 2#3
  6. 2#5

Stable · Rust merge sort

  1. 1#2
  2. 1#4
  3. 1#6
  4. 2#1
  5. 2#3
  6. 2#5
The large number is the sort key; the small number is the item's input position.
C++ stable_sort, Rust sort and Go sort.Stable. Bars moving one at a time are being written back from the buffer; the long swap sequences on the Go side are rotations.

Counts at n=1,000. ‘Writes’ are element moves between the buffer and the array.

inputC++ comparesC++ writesRust comparesRust writesGo comparesGo swaps
random9,5787,6829,7736,88012,41519,730
sorted5,1067,68299901,2290
reversed6,4307,68299909,84213,832
organ pipe5,8567,6821,9981,0007,2209,594

Notice that C++ always makes exactly 7,682 writes regardless of input. The chunk sizes are fixed in advance, so the number of merges is too. Rust looks for runs, so sorted and reversed input take 999 compares, a single pass (reversed costs another 500 swaps to flip). Organ pipe is one rising run and one falling run, so it’s one reversal and one merge. Go uses no extra memory at all but pays for it with close to 20,000 swaps on random input.

It’s hard to call one of these better. Go’s buffer-free stable sort is a consequence of its interface design: any container can be sorted as long as it implements Len, Less and Swap. The price is the performance you’d expect from a language that can move elements directly.

At a glance

C++ (libstdc++)RustGo 1.19
unstable sortstd::sort: introsortsort_unstable: pdqsort, block partitionsort.Sort: pdqsort
insertion sort cutoff162012
depth limit2⌊log⁡2n⌋2\lfloor\log_2 n\rfloorbit length of nnbit length of nn
sorted-input detectionnoyesyes
stable sortstd::stable_sort: merges from chunks of 7, n/2n/2 buffersort: TimSort-style run merging, n/2n/2 buffersort.Stable: blocks of 20 + SymMerge, no buffer
"median-of-3" "introsort" "heapsort" "C++ stable" "Go Stable" "pdqsort" "Rust sort" 0 50000 100000 150000 200000 250000 compares Compares to sort 10,000 already sorted elements (lower is better)

Wrapping up

  • In all three languages the standard sort is a combination of quicksort, insertion sort and heapsort. If quicksort keeps picking bad pivots it hits the depth limit and switches to heapsort, so even the worst case is O(nlog⁡n)O(n \log n).
  • Any deterministic quicksort can be handed a worst-case input using McIlroy’s method. Median-of-3 quicksort made 156× the compares of random input at 10,000 elements; introsort, which is the same pivot rule plus a depth limit, made only 3×.
  • C++‘s std::sort never checks whether its input is already sorted. The pdqsort in Rust and Go 1.19 recognises sorted, reversed and duplicate-heavy input and finishes in close to linear time.
  • The stable sorts are all merge sorts, but they use memory differently. C++ and Rust use a half-size buffer; Go, constrained by sort.Interface, merges in place with rotations.

There’s a surprising amount of code behind a one-line sort() call, all of it looking at the shape of the input. Most of the time you don’t need to know. But if you’re re-sorting data that’s already sorted, sorting data that came from outside, or sorting arrays full of duplicates, which language’s which function you call can make a difference of several times.

QuizChoosing a sort for the job

Choose an answer to see the explanation.

0 of 3 right

  1. A pdqsort range has already ordered pivot candidates. Can it declare the entire range sorted from this signal alone?

  2. An employee list is in name order. You sort it by department and want name order preserved within each department. What should you choose?

  3. The comparison table shows Rust's block partition making slightly more comparisons than Go. Does this alone establish a longer Rust runtime?

Notes

  1. The sort section of the Go 1.19 release notes. The implementation is in src/sort/zsortinterface.go and zsortfunc.go, both generated by gen_sort_variants.go. ↩

  2. M. Douglas McIlroy, “A Killer Adversary for Quicksort”, Software: Practice and Experience 29(4), 1999. ↩

  3. David R. Musser, “Introspective Sorting and Selection Algorithms”, Software: Practice and Experience 27(8), 1997. ↩

  4. Orson R. L. Peters, “Pattern-defeating Quicksort”, arXiv:2106.05123, 2021. Rust’s implementation is in library/core/src/slice/sort.rs. ↩

  5. Stefan Edelkamp, Armin Weiß, “BlockQuicksort: Avoiding Branch Mispredictions in Quicksort”, ESA 2016. ↩

  6. Pok-Son Kim, Arne Kutzner, “Stable Minimum Storage Merging by Symmetric Comparisons”, ESA 2004. ↩

ko.mdx

단축키Keyboard

/ ⌘K
글 검색Search posts
t
밝은/어두운 테마Light or dark theme
l
한국어/영어, 읽던 자리 유지Korean or English, keeping your place
[ ]
이전/다음 절Previous or next section
?
이 목록This list

↑↓ 이동move↵ 열기openesc 닫기close