List 컨테이너의 list::sort함수와 algorithm헤더에 있는 algorithm::sort()는 서로 다르다.

List 컨테이너의 list::sort 함수는 병합 정렬 (MergeSort)로 구현되어 있다.

C++을 사용할 때 STL의 Algorithm 헤더에 있는 정렬 알고리즘은 인트로 정렬(IntroSort)로 되어있고 인트로 정렬은 여러 정렬 알고리즘이 복합적으로 적용된 알고리즘이다.

인트로소트

• 배열을 나눈 각 파티션 크기가 최대 깊이 제한인 2LogN을 넘을 가능성이 있다면 힙소트가 됩니다.
• 파티션의 원소가 16개 이하로 작아지면 삽입 정렬이 됩니다.
• 파티션 크기가 제한 미만이고 너무 작지 않다, 즉 16 ~ 2LogN 크기라면 퀵 정렬을 합니다.

삽입 정렬을 넣은 이유는 삽입 정렬이 작은 배열에 대해서, 정리가 거의 다 된 배열에 대해서 빠른 속도를 가지기 때문입니다.

여기서 머지 소트를 사용하지 않은 이뉴는 N 만큼의 공간이 추가적으로 필요하기에 사용하지 않습니다.