std::sort보다 빠른 C++ 퀵소트가 등장했다
A C++ Quicksort Faster Than std:sort
blqsort는 랜덤 데이터 정렬에서 std::sort를 앞서는 C++ 퀵소트 구현이다. 5천만 개의 double을 Apple M1에서 정렬할 때 std::sort는 1.33초, blqsort는 0.68초가 걸렸고 Intel i5-9300H에서는 4.02초 대 1.32초로 격차가 더 벌어졌다. 분기 없는 파티셔닝, 작은 파티션용 소팅 네트워크, 정교한 피벗 선택이 핵심이며 MIT 라이선스로 GitHub에 공개돼 있다.
컴파일러는 당신의 데이터가 어떤 성질을 지녔는지 알지 못한다. 500 미만인 숫자가 극히 일부라면 분기 버전이 오히려 더 빠를 수도 있다.