1. std::sort

• 비내림차순으로 정렬해주는 <algorithm>의 함수

• 시간복잡도 O(NlogN)을 보장하기 위해 IntroSort를 사용

• 분할정복의 하나인 퀵 정렬은 피벗을 잘못 잡으면(이미 정렬된 데이터 등) 최악의 경우 $O(N^2)$까지 느려질 수 있다

• 따라서 IntroSort는 처음엔 퀵 정렬로 하다가, 재귀 깊이가 너무 깊어지면(데이터가 잘 안 나뉘면) 힙 정렬(Heap Sort)로 전환해서 $O(N \log N)$을 강제로 보장

• 처음부터 데이터 개수가 적거나, 정렬 중 데이터 개수가 적어지면(16개 이하) 삽입 정렬(Insertion Sort)로 마무리해 오버헤드를 줄인다

• 데이터가 적으면 피벗 정하고, 재귀호출하는 등의 과정보다 그냥 단순한 알고리즘의 삽입 정렬이 훨씬 빠르기 때문

2. 왜 퀵 정렬을 먼저?

• 퀵 정렬은 인접한 요소들을 순차적으로 비교하고 스왑함 -> 캐시 히트가 높음

• 힙 정렬은 부모 / 자식을 비교하는데 인덱스가 i에서 2i로 멀리 뜀 -> 캐시 미스 높음

• 따라서 퀵 정렬로 먼저 빠르게 해보다가 느리다면 힙 정렬로 바꾸는 IntroSort를 사용

3. stable_sort

• 일반 sort는 IntroSort(퀵정렬)이기에, 정렬 전의 순서를 보장하지 않는 불안정 정렬

• stable_sort는 병합정렬을 사용하므로 순서를 보장해주는 안정 정렬

• 대신, 병합 정렬 특성 상 임시 버퍼가 필요하므로, 메모리가 부족하다면 성능 문제가 생길 순 있다

• 그리고 임시 버퍼에 값 쓰고 가져오는 과정이 있으므로 캐시 히트율이 높진 않다

• 따라서 캐시 히트가 높은 퀵 정렬이 성능이 엄청 뛰어난 것

• 따라서 성능을 정말 추구해야한다면, 정렬 전의 순서에 대한 값을 원소에 저장해주고, 이 값을 이용해 sort로 정렬한다면 빠르다

Reference

cppreference.com
Wiki