std::sort가 Quick Sort에 기반하고 있다고 알고 있는 많을텐데, 그 이유는 평균적으로 컴퓨터에서 매우 효율적으로 동작한다고 생각하기 때문일것이다.

퀵 정렬의 내부 루프는 대부분의 컴퓨터 아키텍처에서 효율적으로 작동하도록 설계되어 있고(그 이유는 메모리 참조가 지역화되어 있기 때문에 CPU 캐시의 히트율이 높아지기 때문이다.), 대부분의 실질적인 데이터를 정렬할 때 제곱 시간이 걸릴 확률이 거의 없도록 알고리즘을 설계하는 것이 가능하다. 때문에 일반적인 경우 퀵 정렬은 다른 O(n log n) 알고리즘에 비해 훨씬 빠르게 동작한다.

중위 분할법과 개선된 피벗 선택 등 컴퓨터의 특성을 고려한 최적화된 퀵 정렬 알고리즘이 연구되었다.

논리적으로 $O(n\log_2{n})$을 가지는 다른 알고리즘 대신 퀵 정렬이 사용되어 왔다고 알려진다. 그리고 알다시피, 퀵 정렬의 평균 복잡도는 $O(n\log_2{n})$ 최악은 $O(n^2)$이다.

하지만, 문서를 보면

C++ 11이전에는 std::sort를 비교기반 평균$O(n\log_2{n})$으로, 이후에는 $O(n\log_2{n})$으로 명시하고 있다. 즉, 한때는 퀵 정렬이 한 자리 했었겠지만 지금은 아니라는 말이다.

C++ 11이후 표준 라이브러리는 어떤 구현의 변화를 통해 저 약속을 지킬 수 있었을까.

이 글에서 GCC가 David Musser에 의해 개발된 Intro Sort를 참조하고 있다고 말한다.

procedure sort(A : array):
    let maxdepth = ⌊log(length(A))⌋ × 2
    introsort(A, maxdepth)

procedure introsort(A, maxdepth):
    n ← length(A)
    p ← partition(A)  // assume this function does pivot selection, p is the final position of the pivot
    if n ≤ 1:
        return  // base case
    else if maxdepth = 0:
        heapsort(A)
    else:
        introsort(A[0:p], maxdepth - 1)
        introsort(A[p+1:n], maxdepth - 1)

위 의사코드에서, maxdepth의 초기값인 $2log_2{n}$이 재귀호출이 깊어짐에 따라 0에 도달했을때 힙 정렬을 사용하고 있는데, 이로 인해 최악의 시간복잡도가 힙 정렬의 것을 따른다.

실제로 $2log_2{n}$에서 계수 2는 힙 정렬을 사용할 깊이를 결정하는 상수처럼 쓰이며, 컴파일러 및 실행환경에 따라 다른 것 같다. (이 글에서는 1.5로 구현된 부분을 확인 할 수 있다.)

Radix Sort에 기반한다는 일부 의견이 있으나, Radix Sort는 $O(dn)$이라는 데이터 유형(자릿수)를 근거로 비교 연산을 수행하지 않는 알고리즘이므로, 표준문서에 적힌 내용과 상이하다.

또한, std::stable_sort라는 안정정렬을 보장하는 함수가 따로 있는데, 기존의 std::sort가 안정정렬을 보장하지 않기 때문이다. 예를 들면, GCC의 Intro Sort는 퀵 정렬과 힙 정렬를 사용하는 하이브리드 정렬이므로 비교하지 않는 값에 대한 기존 순서를 보장하지 않는다.

번외로, std::stable_sort의 표준은 $O(nlog^2n)$, 공간의 여유가 있을 경우 $O(nlogn)$를 요구하는데, 이는 각각 in-place 합병 정렬과 합병 정렬의 경우를 생각 할 수 있다.

추가적으로, Tim Sort는 현재 가장 많이 사용하고 있는 안정정렬 방법 중 하나이다. 참고.