CS — list sort

📕 05/06 — std::list::sort vs std::sort (왜 멤버 함수가 따로 있는가)

모의면접 주제: “std::list::sort()가 std::sort() 대신 따로 존재하는 이유에 대해서 설명해 주세요” iterator 카테고리 → 알고리즘 선택 → 노드 재연결 vs 데이터 이동 → stable 여부 → forward_list·set/map::find 패턴까지

---

학습 영역 전환점 — 알고리즘과 자료구조의 결합

17번에서 std::find vs std::binary_search로 알고리즘 함수의 분업 설계를 봤다면, 18번은 알고리즘과 자료구조가 만나는 지점입니다. std::sort는 RandomAccessIterator를 요구하는 일반 알고리즘이고, std::list::sort는 연결 리스트의 특성에 맞춘 멤버 함수입니다.

17번  std::find vs binary_search          — 알고리즘 함수 (선형 vs 이분)
─────────────────────────────────────────────────────────────────────
18번  std::list::sort vs std::sort ★      — 멤버 함수 vs 알고리즘 (왜 따로?)
이후  custom comparator / partial_sort    — 정렬 family 확장

이 주제는 17번의 9-1 iterator 카테고리(InputIterator → ForwardIterator → BidirectionalIterator → RandomAccessIterator)를 그대로 이어받습니다. 그리고 set/map에서 멤버 함수 find()를 써야 하는 이유(15번~17번에서 본 그 컨벤션)와도 같은 맥락입니다 — 자료구조의 특성을 알고리즘이 활용할 수 없을 때, 멤버 함수가 따로 존재한다.

---

모의면접 답변

std::sort는 <algorithm> 헤더의 일반 정렬 알고리즘이고, std::list::sort는 std::list의 멤버 함수입니다. 둘이 따로 존재하는 이유는 크게 세 가지입니다.

첫째, iterator 카테고리가 다릅니다. std::sort는 RandomAccessIterator를 요구합니다. 중간에 it + n 같은 점프나 it[i] 인덱싱이 가능해야 quicksort의 partition이 동작하기 때문입니다. 그런데 std::list::iterator는 BidirectionalIterator까지만 지원합니다 — ++it, --it은 되지만 it + n은 안 됩니다. 그래서 std::sort(list.begin(), list.end())는 컴파일 에러가 납니다. 이게 가장 직접적인 이유입니다.

둘째, 정렬 알고리즘 자체가 달라야 효율적입니다. std::sort는 보통 introsort로 구현됩니다 — quicksort로 시작해서 재귀 깊이가 깊어지면 heapsort로 폴백하고, 작은 구간은 insertion sort로 마무리하는 하이브리드입니다. 무작위 접근으로 partition을 빠르게 처리할 수 있다는 전제 위에서 동작합니다. 반면 std::list::sort는 병합 정렬 (merge sort) 기반입니다. 연결 리스트는 포인터 재연결만으로 두 정렬 리스트를 합칠 수 있기 때문에 병합 정렬 (merge sort)가 자연스럽고, 데이터 자체를 옮길 필요가 없습니다.

셋째, 그 결과 비용 구조가 완전히 달라집니다. 둘 다 시간복잡도는 O(n log n)이지만, std::list::sort는 비교 외 데이터 이동 비용이 0입니다 — 노드의 prev/next 포인터만 swap하니까요. std::sort는 partition 과정에서 원소 자체를 swap합니다. 큰 객체를 담은 컨테이너라면 이 차이가 실측 성능에 큰 영향을 줍니다. 그리고 std::list::sort는 stable sort이고 추가 메모리도 O(1)(in-place merge)입니다.

이게 STL 전반의 일관된 설계입니다. set이나 map에서 std::find 대신 멤버 find()를 쓰는 이유와 똑같습니다 — 자료구조의 특성을 알고리즘이 활용할 수 없을 때, 멤버 함수가 따로 존재합니다. forward_list::sort도 같은 이유로 따로 있고, 이런 패턴이 STL의 “멤버 vs 알고리즘 분업” 컨벤션입니다.

---

핵심 개념

분류	키워드	한 줄 정의
함수 정의	std::sort	<algorithm> 헤더, RandomAccessIterator 요구, introsort
	std::list::sort	std::list 멤버 함수, BidirectionalIterator로 OK, 병합 정렬 (merge sort)
	std::forward_list::sort	std::forward_list 멤버 함수, ForwardIterator로 OK, 병합 정렬 (merge sort)
iterator 카테고리	RandomAccessIterator	it + n, it[i] 가능 (vector·deque·array)
	BidirectionalIterator	++it, --it만 가능 (list·set·map)
	ForwardIterator	++it만 가능 (forward_list)
정렬 알고리즘	introsort	quicksort + heapsort + insertion sort 하이브리드. std::sort 구현
	병합 정렬 (merge sort)	두 정렬 리스트를 병합. list::sort 기반 — 포인터 재연결만
	partition (quicksort)	pivot 기준 좌/우 분할. 무작위 접근 필수
시간복잡도	O(n log n)	둘 다 동일. 이론값은 같음
	데이터 이동 비용	std::sort — swap 다수 / list::sort — 0 (포인터만)
안정성	stable sort	동등 원소의 상대 순서 유지. list::sort는 stable
	unstable	std::sort는 비안정. 안정성 필요하면 std::stable_sort
추가 메모리	O(1) in-place	list::sort는 노드 재연결만 — 추가 할당 X
	O(log n) 스택	std::sort (재귀 깊이)
비교 함수	strict weak ordering	둘 다 < 또는 사용자 비교자 요구
컴파일 에러	std::sort(list) 시도	error: no match for 'operator-' 등 — RandomAccess 부재
관련 알고리즘	std::stable_sort	안정 정렬. 추가 메모리 O(n) 또는 O(n log² n)
	std::partial_sort	상위 k개만 정렬. heap 기반 O(n log k)
	std::nth_element	k번째 원소만 제자리에. O(n) 평균
멤버 vs 알고리즘	set/map::find	트리 O(log n) — 알고리즘 std::find는 O(n)이라 손해
	unordered_map::find	해시 O(1) 평균
	list::sort	노드 재연결로 O(n log n) — 알고리즘은 컴파일 X
	forward_list::sort	단방향이라 더더욱 알고리즘 불가
언리얼	Algo::Sort	std::sort 대응. TArray 등 RandomAccess 컨테이너용
	TArray::Sort	멤버 함수. introsort 기반
	TArray::StableSort	안정 정렬 멤버 함수
	TLinkedList	헬퍼 수준. 정렬 멤버 함수는 따로 없음 (수동 구현 필요)

---

목차

1. 핵심 요약 카드
2. 컴파일 에러부터 — 왜 std::sort(list)는 안 되나
3. iterator 카테고리 복기 — 17번 9-1과의 연결
4. 정렬 알고리즘 차이 — introsort vs 병합 정렬 (merge sort)
5. 노드 재연결 — 데이터 이동 비용 0의 의미
6. stable 여부 / 추가 메모리 비교
7. forward_list::sort — 같은 이유로 또 따로
8. 멤버 vs 알고리즘 컨벤션 — set/map::find와 같은 패턴
9. 관련 정렬 family — stable_sort / partial_sort / nth_element
10. 언리얼에서의 정렬 — Algo::Sort / TArray::Sort / TLinkedList
11. 꼬리질문 예상 경로

---

1. 핵심 요약 카드

30초 답변

std::sort        = <algorithm>, RandomAccessIterator 요구, introsort, unstable, swap
std::list::sort  = list 멤버 함수, BidirectionalIterator로 OK, 병합 정렬 (merge sort), stable, 포인터 재연결

이유 3가지:
  ① iterator 카테고리 차이 — list::iterator는 RandomAccess 아님 → 컴파일 에러
  ② 알고리즘이 다름 — quicksort partition은 무작위 접근 필수, list엔 병합 정렬 (merge sort)가 최적
  ③ 비용 구조 — list::sort는 노드 포인터만 재연결, 데이터 이동 0

같은 패턴: set/map::find vs std::find, forward_list::sort
→ "자료구조 특성을 알고리즘이 못 살릴 때 멤버 함수가 따로 존재한다"

꼬리질문 연결 맵

std::list::sort vs std::sort
├── 왜 std::sort(list)는 컴파일 에러? → list iterator는 BidirectionalIterator
│   └── 17번 9-1 iterator 카테고리 (Random Access 필요)
├── 왜 list엔 병합 정렬 (merge sort)가 최적? → 포인터 재연결로 in-place merge가 자연스러움
│   └── quicksort partition은 무작위 접근 필요
├── 둘 다 O(n log n)인데 뭐가 다름? → 데이터 이동 비용 (swap vs 포인터)
├── stable 여부? → list::sort는 stable / std::sort는 unstable
│   └── 안정 정렬 필요하면 std::stable_sort
├── forward_list는? → forward_list::sort 따로 존재 (ForwardIterator라 더 제한적)
├── 같은 패턴? → set/map::find, unordered_map::find (멤버 vs 알고리즘 컨벤션)
└── 정렬 family → stable_sort / partial_sort / nth_element
    └── 13번 vector vs list, 16번 STL 컨테이너 정리로 회귀

---

2. 컴파일 에러부터 — 왜 std::sort(list)는 안 되나

핵심 한 문장

std::sort는 RandomAccessIterator를 요구하는데 std::list::iterator는 BidirectionalIterator라서, 컴파일 단계에서 거부됩니다.

시도하면 어떻게 되나

#include <algorithm>
#include <list>

int main() {
    std::list<int> lst = {3, 1, 4, 1, 5, 9, 2, 6};

    std::sort(lst.begin(), lst.end());   // ★ 컴파일 에러
    // GCC 메시지 (요지):
    // error: no match for 'operator-' (operand types are
    //   'std::_List_iterator<int>' and 'std::_List_iterator<int>')
    //
    // → std::sort 내부에서 (last - first)로 거리 계산을 시도하는데,
    //   list iterator는 - 연산자가 정의돼 있지 않음.
}

→ std::sort 구현 어디선가 mid = first + (last - first) / 2 같은 무작위 점프를 합니다. list iterator는 그 연산을 지원하지 않으므로 템플릿 인스턴스화 단계에서 실패합니다.

정답 — 멤버 함수 사용

std::list<int> lst = {3, 1, 4, 1, 5, 9, 2, 6};
lst.sort();                              // ★ OK — 오름차순
lst.sort(std::greater<int>());           // 내림차순 (비교자)
lst.sort([](int a, int b){ return a > b; });   // 람다도 가능

→ 인자 없이 호출하면 < 기본, 비교자 인자로 strict weak ordering을 만족하는 함수 객체를 받을 수 있습니다.

같은 함수명의 다른 케이스 — vector / deque / array

std::vector<int> v = {3, 1, 4, 1, 5, 9, 2, 6};
std::sort(v.begin(), v.end());   // OK — RandomAccessIterator
// vector에는 멤버 sort()가 없음 — 알고리즘으로 충분하니까

std::deque<int> dq = {3, 1, 4};
std::sort(dq.begin(), dq.end()); // OK — deque도 RandomAccess

std::array<int, 4> ar = {3, 1, 4, 1};
std::sort(ar.begin(), ar.end()); // OK

→ RandomAccess를 지원하는 컨테이너에는 멤버 sort가 없고, 그렇지 않은 list/forward_list에만 멤버 sort가 따로 있다는 비대칭이 핵심입니다. 알고리즘 함수로 충분하면 멤버를 안 만드는 게 STL 컨벤션입니다.

---

3. iterator 카테고리 복기 — 17번 9-1과의 연결

핵심 한 문장

17번에서 정리한 iterator 카테고리(Input → Forward → Bidirectional → RandomAccess)가 그대로 정렬 알고리즘 선택을 결정합니다 — list가 한 단계 부족하다는 사실이 모든 차이의 출발점입니다.

카테고리 표 (17번 9-1 재활용)

카테고리	가능 연산	대표 컨테이너	sort 가능?
Input	++it, *it(읽기 1회)	istream_iterator	X
Forward	+ 여러 번 읽기	forward_list	멤버 sort() 만
Bidirectional	+ --it 역방향	list, set, map	멤버 sort() (list만)
RandomAccess	+ it + n, it[n], it < it2	vector, deque, array	std::sort OK

BidirectionalIterator 자세히 — “한 칸씩 앞·뒤”만 가능하다는 의미

“list::iterator는 BidirectionalIterator다”라는 말은 앞·뒤 양방향으로 한 칸씩만 이동할 수 있다는 뜻입니다. 점프(it+5)나 거리 계산(it2-it1)은 안 됩니다.

지원·비지원 연산

std::list<int> lst = {1, 2, 3, 4, 5};
auto it = lst.begin();

// ✅ 가능 (Bidirectional 보장)
++it;        // 앞으로 1칸    O(1)
--it;        // 뒤로 1칸      O(1)  ← Forward와 다른 점
*it;         // 역참조 읽기/쓰기
it == it2;   // 동등 비교
it != it2;   // 비동등 비교

// ❌ 불가능 (RandomAccess만 가능)
it + 5;      // 컴파일 에러 — 점프
it - it2;    // 컴파일 에러 — 거리 계산
it[3];       // 컴파일 에러 — 인덱싱
it < it2;    // 컴파일 에러 — 순서 비교

“왜” 양방향까지만 가능한가 — list 노드 구조 때문

list 노드:  [prev | data | next] ←→ [prev | data | next] ←→ ...

++it  → 현재 노드의 next 따라가기   O(1)  (포인터 한 번)
--it  → 현재 노드의 prev 따라가기   O(1)  (Bidirectional의 핵심 — Forward에 없는 능력)
it+5  → next를 5번 따라가야 함      O(n)  ← STL이 의도적으로 막음

→ 노드는 메모리에 분산되어 있어서 5번째 노드의 주소를 한 번에 계산할 수가 없습니다. 무작위 접근을 흉내내려면 next를 5번 따라가야 하고 그건 O(n)입니다. STL은 “느린 연산은 아예 표현할 수 없게 하라”는 철학이라 컴파일 단계에서 막습니다.

카테고리 계층 — 상위는 하위의 모든 능력을 포함

RandomAccess  ⊃  Bidirectional  ⊃  Forward  ⊃  Input

RandomAccess  → ++ -- it+n it[n] *it 다 가능
Bidirectional → ++ -- *it       (it+n 없음)
Forward       → ++ *it          (-- 도 없음)
Input         → ++ *it          (1회 읽기만)

→ Bidirectional이 Forward의 상위이므로, ForwardIterator를 요구하는 알고리즘(std::find, std::count 등)은 list iterator로도 동작합니다. 반대로 RandomAccess를 요구하는 std::sort는 list iterator로 안 됩니다.

왜 RandomAccess가 필요한가 — quicksort 시각

quicksort의 핵심은 partition입니다.

[3, 1, 4, 1, 5, 9, 2, 6]
       pivot = 4
       ↓
좌(< 4) | 우(≥ 4) 로 분할
[3, 1, 1, 2] | [4, 5, 9, 6]

분할 과정:
  ① pivot 선택 — 보통 mid = first + (last-first)/2  ← 무작위 접근
  ② 양 끝에서 시작해 left++, right-- 하며 swap     ← --it도 필요
  ③ 재귀 호출 시 left·right 부분 구간 인덱싱       ← it + n

→ list iterator로는 ② 의 양 끝에서 만나기까지의 거리 계산이 O(n)이고, ① 의 mid 점프도 O(n)이어서 이론 시간복잡도부터 깨집니다. 그래서 quicksort는 list에 부적합.

partition 과정 자세히 — quicksort의 심장

partition은 “pivot 기준으로 좌우를 나누는 한 단계“입니다. quicksort 전체 비용의 대부분이 partition에서 발생하고, 안정성·시간복잡도가 모두 partition 방식에 좌우됩니다.

Lomuto partition (단순한 버전, 교과서용)

int partition(arr, lo, hi) {
    int pivot = arr[hi];      // 보통 마지막 원소를 pivot으로
    int i = lo - 1;            // i: 'pivot보다 작은 원소들의 끝'
    for (int j = lo; j < hi; ++j) {
        if (arr[j] < pivot) {
            ++i;
            swap(arr[i], arr[j]);
        }
    }
    swap(arr[i+1], arr[hi]);   // pivot을 가운데로
    return i + 1;              // pivot의 최종 위치
}

시각화:

초기:  [3, 1, 4, 1, 5, 9, 2, 6]    pivot = 6 (마지막)
       i = -1, j = 0

j=0: 3<6 → i=0, swap(a[0],a[0])  [3, 1, 4, 1, 5, 9, 2, 6]
j=1: 1<6 → i=1, swap(a[1],a[1])  [3, 1, 4, 1, 5, 9, 2, 6]
j=2: 4<6 → i=2, swap(a[2],a[2])  [3, 1, 4, 1, 5, 9, 2, 6]
j=3: 1<6 → i=3, swap(a[3],a[3])  [3, 1, 4, 1, 5, 9, 2, 6]
j=4: 5<6 → i=4, swap(a[4],a[4])  [3, 1, 4, 1, 5, 9, 2, 6]
j=5: 9<6 → 아니오 (i 그대로)
j=6: 2<6 → i=5, swap(a[5],a[6])  [3, 1, 4, 1, 5, 2, 9, 6]

마지막 swap(a[6],a[7]):            [3, 1, 4, 1, 5, 2, 6, 9]
                                                  ↑ pivot 자리 확정

좌측 [3, 1, 4, 1, 5, 2] (모두 < 6)  |  우측 [9] (> 6)

→ partition 한 번이면 pivot의 최종 위치가 확정되고, 좌·우는 독립적으로 정렬하면 됩니다 (재귀).

Hoare partition (실제 introsort가 쓰는 버전)

양 끝에서 시작해 안쪽으로 좁혀오며 swap.
좌측 인덱스 →: pivot보다 큰 것 만날 때까지
우측 인덱스 ←: pivot보다 작은 것 만날 때까지
둘이 만나면 종료, 두 구간을 재귀.

장점: swap 횟수가 Lomuto의 약 1/3
단점: pivot이 정확한 자리에 안 가고 partition 경계만 반환 (그래도 정렬은 됨)

pivot 선택 — median-of-three

나쁜 pivot → quicksort가 O(n²)로 떨어짐
            (예: 이미 정렬된 입력 + '첫 원소'를 pivot으로 잡는 방식)

introsort의 방어 장치:
  ① median-of-three: 첫·중간·끝 세 원소 중 중간값을 pivot으로
  ② 재귀 깊이 2*log₂(n) 초과 시 heapsort 폴백 → 최악도 O(n log n) 보장

왜 partition은 RandomAccess가 필수인가 — 한 번 더 정리

중간값 선택:  mid = first + (last - first) / 2     ← it + n
양 끝 swap:   swap(*lo, *hi--), ++lo               ← 양방향 + 인덱스
재귀 호출:    partition(arr, lo, mid-1)             ← 부분 구간 인덱싱

이 연산들이 모두 O(1)이어야 partition 한 번이 O(n)으로 끝남.
list iterator는 it+n이 O(n) → partition 한 번이 O(n²) → quicksort 자체가 O(n³)
→ 그래서 list엔 quicksort/introsort 자체가 부적합.

왜 병합 정렬 (merge sort)가 list에 최적인가 — 직관

병합 정렬 (merge sort)의 두 정렬 리스트 병합(merge) 단계는:

A: 1 → 3 → 5
B: 2 → 4 → 6
       ↓ merge
결과: 1 → 2 → 3 → 4 → 5 → 6

연결 리스트면 → 노드의 next 포인터만 골라서 연결 (데이터 이동 없음)
배열이면      → 새 배열에 복사해야 함 (추가 메모리 O(n))

→ merge가 list에서는 in-place로 자연스럽게 동작합니다. 연결 리스트의 구조 자체가 병합 정렬 (merge sort)에 최적화돼 있다고 봐도 됩니다.

---

4. 정렬 알고리즘 차이 — introsort vs 병합 정렬 (merge sort)

std::sort — introsort (1997, Musser)

세 알고리즘을 단계별로 폴백하는 하이브리드. C++ 표준이 명시적으로 introsort를 요구하진 않지만, 대부분의 표준 라이브러리(libstdc++, libc++, MSVC)가 채택.

입력 → 재귀 깊이 추적
  ├── 깊이 < 2*log₂(n) AND 구간 크기 > 16
  │     └── quicksort (median-of-three pivot)
  ├── 깊이 ≥ 2*log₂(n)  ← worst case 진입
  │     └── heapsort 로 폴백 (보장된 O(n log n))
  └── 작은 구간 (≤ 16)
        └── insertion sort 로 마무리 (캐시 친화적)

• 시간복잡도: 평균 O(n log n), 최악도 O(n log n) (heapsort 폴백 덕분)
• 공간복잡도: O(log n) (재귀 스택)
• stable: No — quicksort partition이 동등 원소 순서를 깸
• 요구: RandomAccessIterator

insertion sort 자세히 — introsort가 작은 구간에서 마무리로 쓰는 알고리즘

카드 게임에서 손에 든 카드를 정렬하는 방식과 같습니다. 한 장씩 뽑아 이미 정렬된 부분의 알맞은 자리에 끼워 넣습니다.

동작 시각화

입력: [5, 2, 4, 6, 1, 3]
       └─ | 왼쪽이 정렬된 prefix, 오른쪽이 미정렬

step 1: [5 | 2, 4, 6, 1, 3]      ← 첫 원소는 자체로 정렬
step 2: [2, 5 | 4, 6, 1, 3]      ← 2를 5 앞으로 이동
step 3: [2, 4, 5 | 6, 1, 3]      ← 4를 5 앞으로 이동
step 4: [2, 4, 5, 6 | 1, 3]      ← 6은 그대로
step 5: [1, 2, 4, 5, 6 | 3]      ← 1을 맨 앞까지 이동
step 6: [1, 2, 3, 4, 5, 6]       ← 3을 4 앞으로 이동

핵심: | 왼쪽 prefix는 항상 정렬 상태를 유지하며, 오른쪽 원소를 하나씩 끼움.

의사코드

for (int i = 1; i < n; ++i) {
    auto key = arr[i];
    int j = i - 1;
    while (j >= 0 && arr[j] > key) {   // 큰 원소들을 한 칸씩 우측으로 밀기
        arr[j + 1] = arr[j];
        --j;
    }
    arr[j + 1] = key;                   // 빈 자리에 key 삽입
}

복잡도와 특성

항목	값	메모
평균 시간	O(n²)	끼워 넣을 때마다 평균 n/2번 비교·이동
최악 시간	O(n²)	역순 입력
최선 시간	O(n)	이미 정렬된 입력 — 비교만 n-1번
공간	O(1)	in-place
stable	Yes	> 비교만 쓰면 동등 원소가 자기 자리에 멈춤

introsort가 작은 구간에서 insertion sort를 쓰는 이유

구간 크기 ≤ 16 이면 quicksort 재귀 대신 insertion sort 호출

이유:
  ① 재귀 오버헤드 제거 — 작은 구간엔 함수 호출 비용이 더 큼
  ② 캐시 친화 — 16개 정도면 L1 캐시에 그대로 들어감
  ③ 거의 정렬된 데이터에 강함 — quicksort partition을 거친 작은 구간은
     이미 부분적으로 정렬됐을 가능성이 높음 → insertion sort의 best case에 근접

→ insertion sort는 작은 데이터 + 거의 정렬된 데이터에서 quicksort보다 빠릅니다. 이 두 조건이 introsort 막바지에 항상 만족되기 때문에 마무리용으로 쓰입니다.

std::list::sort — 병합 정렬 (merge sort)

연결 리스트 전용 in-place 병합 정렬 (merge sort). 표준은 알고리즘을 명시하지 않지만, 반드시 stable + O(n log n) 을 요구. 사실상 병합 정렬 (merge sort)가 정답.

list::sort(범위)
  ① 리스트를 절반으로 분할 (slow/fast 포인터 또는 노드 카운트)
  ② 각 절반을 재귀 정렬
  ③ merge — 두 정렬 리스트의 head를 비교하며 작은 쪽 노드를 결과 리스트 끝에 연결
            (포인터 재배치만, 데이터 이동 X)

• 시간복잡도: O(n log n) 보장 (worst·average·best 동일)
• 공간복잡도: O(1) — in-place (노드 재연결만)
• stable: Yes — merge 단계에서 동등 원소면 왼쪽(앞쪽)을 먼저 선택
• 요구: BidirectionalIterator (사실은 ForwardIterator로도 충분)

병합 정렬 (merge sort) 자세히 — 분할 정복의 교과서 사례

병합 정렬은 “나눠서 각각 정렬한 뒤 합친다“는 분할 정복(divide and conquer) 알고리즘입니다. list::sort의 기본 구현이며, std::stable_sort도 사실상 같은 계열입니다.

3단계 — 분할(Divide) / 정복(Conquer) / 결합(Merge)

입력: [3, 1, 4, 1, 5, 9, 2, 6]

[1] 분할 (Divide)
    절반으로 쪼갬:  [3, 1, 4, 1] | [5, 9, 2, 6]
    더 쪼갬:       [3, 1] [4, 1] | [5, 9] [2, 6]
    1개까지:       [3][1] [4][1] | [5][9] [2][6]

[2] 정복 (Conquer)
    1개짜리는 자체로 정렬된 상태 (base case)

[3] 결합 (Merge — 핵심)
    [1, 3] [1, 4]  | [5, 9] [2, 6]    ← 두 정렬 리스트를 비교하며 머지
    [1, 1, 3, 4]   | [2, 5, 6, 9]
    [1, 1, 2, 3, 4, 5, 6, 9]            ← 최종

merge 단계가 어떻게 동작하나 (stable의 비밀)

A: [1, 3]      a 포인터: → 1
B: [1, 4]      b 포인터: → 1
결과: []

step 1: *a=1, *b=1 → 동등 → '<'만 비교하므로 b가 a보다 작지 않음 → a를 먼저 선택
                                                                    ★ stability 핵심
        결과: [1(A)], a→3
step 2: *a=3, *b=1 → b 작음 → b 선택, 결과: [1(A), 1(B)], b→4
step 3: *a=3, *b=4 → a 작음 → a 선택, 결과: [1(A), 1(B), 3], a 끝
step 4: B의 남은 부분 [4] 이어붙임 → [1(A), 1(B), 3, 4]

→ 코드 한 줄(if (*b < *a)로 b를 먼저 선택)에서 <만 쓰고 <=를 쓰지 않으면 동등 원소일 때 a(왼쪽 시퀀스)가 항상 먼저 나오게 되어 안정성이 자연스럽게 보존됩니다.

시간복잡도 분석 (마스터 정리)

T(n) = 2 * T(n/2) + O(n)
       └─ 두 절반 ─┘   └ merge 한 번 ┘

깊이 = log₂ n  (절반씩 쪼개니까)
각 깊이의 작업량 = O(n)  (그 깊이의 모든 머지를 합치면 n개 비교)
→ 총 비용 = O(n log n)

worst = average = best = O(n log n)  ← quicksort와 달리 입력 모양에 무관

두 가지 구현 방식 — top-down vs bottom-up

방식	동작	특징
Top-down (재귀)	큰 범위를 절반으로 쪼개며 재귀 호출	직관적. O(log n) 스택 사용
Bottom-up (반복)	1개씩 짝지어 머지 → 2개씩 → 4개씩 …	스택 없이 반복문. 캐시 친화적

→ std::list::sort는 보통 bottom-up 방식으로 구현됩니다 (libstdc++ 등). 재귀 스택을 안 써서 O(1) 추가 메모리를 보장하기 좋고, 머지 단위를 1, 2, 4, 8, 16 … 으로 키워가며 진행합니다.

왜 list에 자연스러운가 — 결정타

배열 머지: 두 정렬된 부분을 머지하려면 결과 담을 새 배열 필요 (O(n) 추가 메모리)
           in-place로도 가능하지만 알고리즘이 매우 복잡 (Knuth, Pratt 등)

list 머지: 두 정렬된 리스트의 노드 next 포인터만 다시 잇기
           → 추가 메모리 O(1), 데이터 이동 0, 안정성 자연스러움

→ 연결 리스트의 자료구조 자체가 병합 정렬의 머지 단계와 완벽히 맞물립니다. 이게 std::list가 sort 멤버 함수로 병합 정렬 (merge sort)을 채택한 가장 강력한 이유입니다.

단점 — 캐시 친화성

배열 + 병합 정렬: 데이터가 연속된 메모리 → 캐시 히트율 높음
list + 병합 정렬: 노드가 힙 곳곳에 분산 → 캐시 미스 빈발

그래서 vector + std::sort(introsort)가 list + list::sort보다 보통 5~10배 빠름.
list::sort는 어디까지나 "list를 써야만 하는 상황에서의 최선"이지,
list가 vector보다 정렬에서 빠르다는 의미가 절대 아님.

→ 13번에서 본 “list가 정당화되는 시나리오”(큰 객체 + 잦은 splice + iterator 안정성)에 들어맞을 때만 list::sort의 이점이 발현됩니다.

비교 표

항목	std::sort (introsort)	std::list::sort (병합 정렬 / merge sort)
알고리즘	quicksort + heapsort + insertion sort	병합 정렬 (merge sort)
시간복잡도 (평균)	O(n log n)	O(n log n)
시간복잡도 (최악)	O(n log n) (heapsort 폴백)	O(n log n)
공간복잡도	O(log n) 재귀	O(1) in-place
안정성	Unstable	Stable
데이터 이동	swap 다수 (객체 복사·이동)	0 (노드 포인터 재연결)
캐시 친화성	매우 높음 (연속 메모리)	낮음 (노드 분산)
비교 함수	strict weak ordering	strict weak ordering
iterator 요구	RandomAccess	Bidirectional

→ 이론 복잡도는 같지만, 데이터 이동 비용과 캐시 친화성에서 둘은 정반대 특성을 보입니다.

---

5. 노드 재연결 — 데이터 이동 비용 0의 의미

핵심 한 문장

std::list::sort는 노드 자체를 옮기지 않고 prev/next 포인터만 재연결해서 정렬합니다. 큰 객체를 담고 있을수록 이 차이가 실측 성능을 가릅니다.

시각화 — merge 한 단계

초기 (두 정렬 리스트)
A: [1] ←→ [3] ←→ [5]
B: [2] ←→ [4] ←→ [6]

merge 진행 (포인터만 재배치)
            ┌────────────────┐
[1] ──next──┘                ▼
            ┌────────────────[2]──next─→ ...
[3] ──next──┘
                            (객체 1, 3, 5, 2, 4, 6 의 메모리 주소는 그대로!)

결과 (단일 정렬 리스트)
[1] ←→ [2] ←→ [3] ←→ [4] ←→ [5] ←→ [6]

→ 노드 자체는 처음 할당된 자리에 그대로, 단지 next/prev가 다른 노드를 가리키게 바뀐 것뿐입니다. 객체 복사 생성자나 이동 생성자는 한 번도 호출되지 않습니다.

vector + std::sort 와의 비교

struct LargeObject {
    char data[1024];
    bool operator<(const LargeObject& o) const { /* ... */ }
};

// vector 케이스
std::vector<LargeObject> v(10000);
std::sort(v.begin(), v.end());
// → partition·merge 단계마다 1024바이트 객체를 swap (memcpy 다수)
// → 실측: 데이터 이동 비용이 비교 비용보다 훨씬 큼

// list 케이스
std::list<LargeObject> lst(10000);
lst.sort();
// → 노드 포인터(8바이트 × 2)만 재배치
// → 객체 자체의 1024바이트는 한 번도 안 옮김

→ 이게 list가 정당화되는 거의 유일한 실용적 시나리오입니다 (13번 6장 참고). “큰 객체 + 잦은 정렬·splice + iterator 안정성”이 동시에 만족돼야 하지만, 매우 드물긴 합니다.

iterator 안정성 (덤)

list::sort는 iterator를 무효화하지 않습니다. 재배치 후에도 노드 자체가 그대로 살아있으니 노드를 가리키던 iterator는 여전히 같은 값을 가리킵니다 (위치는 바뀌었지만).

std::list<int> lst = {3, 1, 4, 1, 5};
auto it = std::next(lst.begin());   // 두 번째 원소 = 1
lst.sort();
// lst = {1, 1, 3, 4, 5}
*it;   // 여전히 1 (노드는 살아있음)

→ vector였다면 std::sort 후 iterator가 가리키는 값이 완전히 달라지거나 무효화될 수 있습니다.

---

6. stable 여부 / 추가 메모리 비교

stable이 뭔지 풀어서 — “동등 원소의 상대 순서 유지”의 진짜 의미

한 줄로: 정렬 키는 같은데 다른 정보는 다른 두 원소가, 입력에서 어느 쪽이 앞이었는지를 정렬 후에도 그대로 보존하는 것.

“동등”이 헷갈리는 이유

“동등 원소”라는 말이 “완전히 똑같은 원소”처럼 들리지만, 정확히는 정렬 비교 함수가 둘 사이에 우열을 가리지 못하는 원소입니다. 정렬 키만 같고 다른 데이터(이름·날짜 등)는 얼마든지 다를 수 있습니다.

struct Employee { std::string name; int dept; };
// 부서(dept)로만 정렬하면 — 부서가 같은 두 사원은 cmp 입장에선 "동등"
// (이름이 달라도 cmp는 신경 X)

사례로 보는 stable vs unstable

입력: [Alice/팀1, Bob/팀2, Charlie/팀1, Dave/팀2, Eve/팀1]
       (팀 번호로만 정렬)

stable 결과 (보장):
[Alice/팀1, Charlie/팀1, Eve/팀1, Bob/팀2, Dave/팀2]
  → 팀1 안: Alice → Charlie → Eve  (입력 순서 그대로)
  → 팀2 안: Bob → Dave             (입력 순서 그대로)

unstable 결과 (예시 1가지):
[Eve/팀1, Alice/팀1, Charlie/팀1, Dave/팀2, Bob/팀2]
  → 팀1 안 순서가 뒤섞임 (보장이 없을 뿐, 우연히 유지될 수도 있음)

→ unstable이라고 해서 항상 순서가 깨지는 게 아니라, 보장하지 않는다는 뜻입니다. 같은 입력 + 같은 알고리즘이면 결과가 같을 수 있지만 일반적으로는 의존하면 안 됩니다.

왜 실무에서 중요한가 — 다단계 정렬

요구: "사원을 부서별로, 같은 부서 안에선 입사일 순서로 정렬"

해결책 (stable_sort 활용):
  ① 먼저 입사일로 정렬 (sort 또는 stable_sort 아무거나)
  ② 그 다음 부서로 stable_sort
  → ②가 stable이면 ①에서 만든 입사일 순서가 같은 부서 안에서 유지됨

만약 ②를 unstable sort로 하면 ①의 정렬이 무의미해짐.

→ 다단계 정렬·외부에서 미리 만든 순서 보존 같은 시나리오에서 stable 여부가 정답을 가릅니다.

stable의 형식 정의

동등한 원소(!(a < b) && !(b < a)인 원소)들의 상대적 순서를 입력 그대로 유지하는 정렬.

std::vector<std::pair<int, char>> v = {
    {1, 'a'}, {2, 'b'}, {1, 'c'}, {2, 'd'}, {1, 'e'}
};
auto cmp = [](const auto& x, const auto& y){ return x.first < y.first; };

std::sort(v.begin(), v.end(), cmp);
// 가능 결과 1: (1,a) (1,c) (1,e) (2,b) (2,d)   ← 운 좋게 유지
// 가능 결과 2: (1,e) (1,a) (1,c) (2,d) (2,b)   ← 순서 깨짐 — 보장 X

std::stable_sort(v.begin(), v.end(), cmp);
// 항상: (1,a) (1,c) (1,e) (2,b) (2,d)         ← 보장

list::sort는 왜 stable 보장인가

병합 정렬 (merge sort)의 merge 단계에서 두 부분이 동등할 때 왼쪽(앞)을 먼저 선택하도록 구현하면 자연스럽게 stable이 됩니다.

// merge 의사코드
while (a != A.end() && b != B.end()) {
    if (*b < *a) take_from(b);   // ← b가 *엄격히* 작을 때만 b를 먼저
    else         take_from(a);   // 동등하면 a (왼쪽)를 먼저 → stability 유지
}

표준은 std::list::sort에 stable 보장을 명시합니다. std::sort는 stable을 보장하지 않으므로 stable이 필요하면 std::stable_sort를 써야 합니다.

추가 메모리 비교

함수	추가 메모리	비고
std::sort	O(log n)	재귀 스택
std::list::sort	O(1)	in-place 노드 재연결
std::stable_sort	O(n) 또는 O(n log² n)	추가 버퍼 확보 가능 시 O(n), 실패 시 O(n log² n) 시간

→ std::stable_sort는 메모리를 못 잡으면 시간복잡도가 O(n log² n)로 떨어집니다 (in-place 병합 정렬 (merge sort)). 반면 list::sort는 노드 재연결이 자연스럽게 in-place라 항상 O(n log n) + O(1).

비교 정리

항목	std::sort	std::list::sort	std::stable_sort
stable	No	Yes	Yes
추가 메모리	O(log n)	O(1)	O(n) 또는 O(n log² n) 시간
시간 (보장)	O(n log n)	O(n log n)	O(n log n) 또는 O(n log² n)

---

7. forward_list::sort — 같은 이유로 또 따로

핵심 한 문장

std::forward_list(단방향 연결 리스트)는 ForwardIterator만 지원해서 std::sort는 물론 BidirectionalIterator가 필요한 일부 알고리즘도 못 씁니다. 그래서 forward_list::sort도 멤버 함수로 따로 있습니다.

시그니처

template <class Compare>
void forward_list<T>::sort(Compare comp);

template <>
void forward_list<T>::sort();   // 기본 < 비교

카테고리 비교

컨테이너	iterator	멤버 sort	알고리즘 sort
vector, deque, array	RandomAccess	없음 (불필요)	std::sort OK
list	Bidirectional	list::sort	컴파일 에러
forward_list	Forward	forward_list::sort	컴파일 에러

forward_list만의 추가 제약

• --it 안 됨 → 끝에서부터 역방향 순회 불가
• size() 멤버 함수도 없음 (O(1) 보장 불가라 의도적으로 제거)
• 그래서 정렬 구현은 노드 카운트를 직접 세거나 bottom-up 병합 정렬 (merge sort) 사용

→ 단방향이라 더더욱 외부 알고리즘이 손댈 수가 없는 자료구조이고, 멤버 함수가 따로 있어야 하는 당위성이 더 강합니다.

같은 패턴의 멤버 함수들

list::sort()       / forward_list::sort()       — 정렬
list::merge(other) / forward_list::merge(other) — 정렬된 리스트 병합 (노드 이전)
list::splice(...)  / forward_list::splice_after(...)  — 노드 이전
list::unique()     / forward_list::unique()     — 인접 중복 제거
list::reverse()    / forward_list::reverse()    — 역순화

→ 모두 노드 포인터 재연결로 O(?) 비용을 줄일 수 있는 연산들. 알고리즘으로 구현하면 데이터 이동이 발생하지만, 멤버 함수는 포인터만 만집니다.

---

8. 멤버 vs 알고리즘 컨벤션 — set/map::find와 같은 패턴

핵심 한 문장

“자료구조의 특성을 알고리즘이 활용할 수 없을 때, 멤버 함수가 따로 존재한다” — 이게 STL 전체에 일관되게 흐르는 설계 원칙입니다.

같은 컨벤션의 사례 모음

자료구조	멤버 함수	알고리즘 함수	이유
std::set / std::map	find() O(log n)	std::find O(n)	RB-Tree 구조 활용
std::unordered_map	find() O(1) 평균	std::find O(n)	해시 버킷 점프
std::list	sort() O(n log n) stable	std::sort 컴파일 에러	노드 재연결 + iterator 카테고리
std::forward_list	sort() O(n log n) stable	std::sort 컴파일 에러	단방향 + 노드 재연결
std::list	merge(), splice(), unique(), reverse()	알고리즘은 데이터 이동	노드 재연결
std::set / std::map	lower_bound(), upper_bound(), equal_range()	알고리즘 버전 존재하나 멤버가 더 빠름	트리 구조 활용
std::set / std::map	count() O(log n)	std::count O(n)	트리 구조 활용

한 줄로

멤버 함수가 있다면 거의 항상 그게 더 빠르거나, 더 안전하거나, 알고리즘이 아예 못 쓰는 케이스다.
                                                          ─ STL 멤버 vs 알고리즘 컨벤션

결정 흐름

이 컨테이너에 sort/find/count/equal_range 등 멤버 함수가 있나?
        │
   ┌────┴────┐
   예         아니오
   │           │
멤버 함수      알고리즘 함수 사용
사용 (★)     (vector·deque·array 같은 RandomAccess)
   │
"자료구조 특성을 살려 더 빠르거나, 알고리즘은 컴파일도 안 됨"

---

9. 관련 정렬 family — stable_sort / partial_sort / nth_element

비교 표

함수	시간복잡도	추가 메모리	stable	용도
std::sort	O(n log n)	O(log n)	No	일반 정렬
std::stable_sort	O(n log n) 또는 O(n log² n)	O(n) 시도	Yes	안정 정렬 필요
std::partial_sort	O(n log k)	O(1)	No	상위 k개만 정렬
std::nth_element	O(n) 평균	O(1)	No	k번째 원소만 제자리에
std::sort_heap	O(n log n)	O(1)	No	heap → 정렬 변환
std::list::sort	O(n log n)	O(1)	Yes	list 전용 in-place merge
std::forward_list::sort	O(n log n)	O(1)	Yes	forward_list 전용

핵심 코드 예시

std::vector<int> v = {3, 1, 4, 1, 5, 9, 2, 6};

// (1) 일반 정렬 — 가장 자주 씀
std::sort(v.begin(), v.end());
// {1, 1, 2, 3, 4, 5, 6, 9}

// (2) 안정 정렬 — 동등 원소 순서 유지 필요
std::stable_sort(v.begin(), v.end());

// (3) 상위 3개만 정렬 (전체 정렬은 안 함)
std::partial_sort(v.begin(), v.begin() + 3, v.end());
// {1, 1, 2, ...뒤는 정렬 안 됨...}

// (4) k번째 원소(중앙값 등) 만 제자리에
std::nth_element(v.begin(), v.begin() + v.size()/2, v.end());
// 중앙값이 v[n/2]에 위치, 좌측은 더 작거나 같음, 우측은 더 크거나 같음 — 평균 O(n)

→ 상위 k개만 필요하면 partial_sort, k번째 원소만 필요하면 nth_element. 전체 정렬보다 빠릅니다.

안정성이 중요한 케이스

struct Employee { std::string name; int dept; };
std::vector<Employee> emps = { ... };

// 부서별로 정렬하되 같은 부서 안에선 입력 순서 유지하고 싶다
std::stable_sort(emps.begin(), emps.end(),
    [](const auto& a, const auto& b){ return a.dept < b.dept; });
// 같은 dept 안에선 원래 입력 순서대로 (이름순 등)

→ std::sort였다면 같은 부서 안에서 임의의 순서가 되어버립니다.

---

10. 언리얼에서의 정렬 — Algo::Sort / TArray::Sort / TLinkedList

대응 표

std::	Unreal Algo:: / 멤버	비고
std::sort	Algo::Sort(Range)	introsort 기반
std::sort	TArray::Sort() (멤버)	안정성 보장 X
std::stable_sort	Algo::StableSort(Range)	안정 정렬
std::stable_sort	TArray::StableSort() (멤버)	안정 정렬
std::partial_sort	(직접 대응 없음)	Algo::HeapSort + 자르기 등 조합
std::nth_element	(직접 대응 없음)	수동 구현
std::list::sort	(대응 없음)	TLinkedList에 sort 멤버 함수 X — 수동 구현

코드 예시

#include "Algo/Sort.h"
#include "Algo/StableSort.h"

TArray<int32> Arr = {3, 1, 4, 1, 5, 9, 2, 6};

// (1) 멤버 함수 — 가장 일반적
Arr.Sort();                                  // 기본 < 오름차순
Arr.Sort([](int32 A, int32 B){ return A > B; });  // 내림차순 람다

// (2) Algo::Sort — std::sort 대응
Algo::Sort(Arr);
Algo::Sort(Arr, [](int32 A, int32 B){ return A < B; });

// (3) 안정 정렬
Arr.StableSort();
Algo::StableSort(Arr);

TLinkedList — std::list 대응이 1급이 아닌 이유

// 언리얼의 TLinkedList는 의도적으로 가벼운 헬퍼 수준
TLinkedList<int32> List;
// → Sort() 멤버 함수 없음
// → 정렬이 필요하다면 TArray<int32>로 옮기거나 수동 병합 정렬 (merge sort)

→ 언리얼이 cache 친화적 자료구조(TArray)를 1급으로 두고 연결 리스트를 부수적으로 다루는 철학(13번 7장 참고)이 정렬에서도 그대로 드러납니다. 게임 엔진은 매 프레임 캐시 효율이 중요한데 list 노드 분산은 적합하지 않으니까요.

차이점 요약

• 언리얼은 std::list::sort 같은 연결 리스트 전용 정렬을 지원하지 않음 — 정렬이 필요한 컬렉션은 TArray 사용
• Sort() 멤버 함수와 Algo::Sort() 둘 다 존재하지만 멤버 함수가 컨벤션
• TArray::Sort()는 stable이 아님, 안정 정렬이 필요하면 명시적으로 StableSort()

---

11. 꼬리질문 예상 경로

Q1. “왜 std::sort는 RandomAccessIterator를 요구하나요? 그냥 다 받게 만들면 안 되나요?”

introsort의 핵심인 quicksort partition이 무작위 접근에 의존하기 때문입니다. mid pivot 선택, 양 끝에서 만나는 swap, 재귀 분할 시 부분 구간 인덱싱이 모두 it + n이나 it - it 같은 random access 연산을 씁니다. ForwardIterator로 만들면 이 연산들이 O(n)이 되어 quicksort 자체가 O(n²) 으로 떨어집니다. 그래서 RandomAccess 컨테이너용 빠른 정렬은 알고리즘으로, 연결 리스트용 병합 정렬 (merge sort)은 멤버 함수로 분리한 게 STL의 설계입니다.

Q2. “list::sort는 왜 병합 정렬 (merge sort)을 쓰나요? quicksort나 heapsort는 안 되나요?”

연결 리스트의 구조와 가장 잘 맞는 알고리즘이 병합 정렬 (merge sort)이기 때문입니다. 두 정렬 리스트의 merge가 포인터 재연결만으로 O(n) in-place로 끝납니다. quicksort는 partition에 무작위 접근이 필요해 list에선 비효율적이고, heapsort도 마찬가지로 무작위 접근 기반 자료구조(heap)가 필요합니다. 병합 정렬 (merge sort)는 순차 접근만으로 동작하고 안정성도 자연스럽게 따라옵니다. 더해서 표준은 list::sort에 stable + O(n log n) 보장을 요구하는데 이걸 만족하는 게 사실상 병합 정렬 (merge sort)입니다.

Q3. “둘 다 O(n log n)인데 실제로 어떤 차이가 있나요?”

이론 복잡도는 같지만 실측 비용 구조가 다릅니다. 첫째, 데이터 이동 비용입니다. std::sort는 partition·merge 과정에서 객체 자체를 swap합니다. 큰 객체를 담은 컨테이너라면 매 swap마다 memcpy나 move 생성자가 호출됩니다. list::sort는 prev/next 포인터 두 개만 재배치하니 객체는 한 번도 안 옮깁니다. 둘째, 캐시 친화성은 정반대로 vector가 압도적입니다. 셋째, iterator 안정성은 list가 우위입니다. 그래서 큰 객체 + 자주 정렬 + 안정성 필요 케이스에선 list가, 일반적인 경우엔 vector + sort가 정답입니다.

Q4. “list::sort는 stable인데 std::sort는 unstable인 이유는?”

알고리즘 차이입니다. 병합 정렬 (merge sort)는 자연스럽게 stable입니다 — merge 단계에서 동등한 원소면 왼쪽(앞쪽) 것을 먼저 선택하도록 < 만 쓰고 <= 를 안 쓰면 자동으로 안정성이 유지됩니다. 반면 quicksort의 partition은 pivot 좌우로 원소를 swap하는 과정에서 동등 원소의 상대 순서가 깨집니다. 그래서 introsort 전체로 봤을 때 std::sort는 stable을 보장할 수 없습니다. 안정성이 필요하면 std::stable_sort를 쓰면 되는데, 이건 추가 메모리 O(n)이 필요하거나 메모리를 못 잡을 때 시간이 O(n log² n)로 떨어집니다.

Q5. “forward_list에도 sort가 따로 있나요?”

네, std::forward_list::sort()가 멤버 함수로 따로 있습니다. forward_list는 ForwardIterator만 지원해서 --it도 안 되니 list보다 더 제약이 큽니다. 그래서 외부 알고리즘이 손댈 수가 없고, 단방향 연결 리스트의 구조를 활용한 병합 정렬 (merge sort)를 멤버로 제공하는 게 유일한 방법입니다. 같은 이유로 merge, splice_after, unique, reverse 같은 연산도 모두 멤버 함수로 있습니다.

Q6. “set이나 map은 정렬된 상태로 유지되는데 sort 멤버 함수가 없는 이유는?”

자료구조 자체가 삽입 시점에 이미 정렬을 유지하기 때문입니다. std::set과 std::map은 RB-Tree 기반이고 삽입할 때 트리 회전과 재색칠로 정렬 불변식을 유지합니다. 따라서 별도의 sort 호출이 필요 없습니다. 이게 list와의 결정적 차이입니다 — list는 임의 순서로 push할 수 있으니 정렬이 별도 연산이지만, set/map은 정렬 상태 자체가 자료구조의 invariant입니다.

Q7. “std::sort 대신 std::list::sort를 쓰면 항상 빠른가요?”

아닙니다. list 자체가 vector보다 거의 항상 느립니다. 1M개 정수 정렬 벤치마크에서 vector::sort가 list::sort보다 보통 5~10배 빠릅니다. 캐시 친화성 때문입니다. list가 정당화되는 케이스는 13번에서 정리한 그대로 — 매우 큰 객체 + 잦은 splice/merge + iterator 안정성 절대 필요. 평범한 정렬 워크로드면 vector + std::sort가 압승입니다. “list::sort가 따로 있다”는 사실은 list를 써야 할 때의 정렬 방법이지, list를 쓸 이유가 아닙니다.

Q8. “stable_sort와 list::sort가 둘 다 stable이면 차이는?”

동작 컨테이너가 다릅니다. std::stable_sort는 RandomAccessIterator 컨테이너(vector·deque·array)용 안정 정렬이고, std::list::sort는 list 전용입니다. 추가 메모리도 다릅니다 — stable_sort는 O(n) 추가 버퍼를 시도하고 실패하면 시간이 O(n log² n)로 떨어지지만, list::sort는 노드 재연결만으로 항상 O(1) 추가 메모리 + O(n log n) 시간을 보장합니다.

Q9. “그럼 list::sort는 std::stable_sort보다 메모리 효율이 좋다는 건가요?”

메모리 효율 측면에서는 그렇습니다. 하지만 list 자체가 노드마다 prev/next 포인터 16바이트 + 힙 할당 헤더를 갖고 있어 메모리 총량은 vector보다 훨씬 많이 씁니다 (13번 5장). 정렬 중 추가로 쓰는 임시 메모리만 적을 뿐이고, 베이스 메모리 푸터프린트는 vector가 압승입니다. 그래서 메모리 효율이라는 단어를 어떻게 해석하느냐에 따라 답이 달라집니다.

Q10. “TLinkedList는 왜 Sort 멤버 함수가 없나요?”

언리얼이 의도적으로 연결 리스트를 1급 자료구조로 만들지 않았기 때문입니다. 게임 엔진은 매 프레임 수만 개 객체를 순회하는데 list 노드 분산은 캐시 미스로 직결됩니다. 그래서 언리얼은 TArray를 1급으로 두고, TLinkedList/TDoubleLinkedList는 가벼운 헬퍼로만 제공합니다. 정렬이 필요하다면 보통 TArray로 변환하거나 직접 merge sort를 구현합니다. 이게 13번에서 본 “캐시 친화성 우선” 철학의 또 다른 발현입니다.

---

핵심 요약 카드 (재게재)

std::sort        = <algorithm>, RandomAccess 요구, introsort, unstable
                   객체 swap 다수, O(log n) 추가 메모리, 캐시 친화

std::list::sort  = list 멤버, Bidirectional로 OK, 병합 정렬 (merge sort), stable
                   포인터 재연결만, O(1) 추가 메모리, iterator 무효화 X

std::forward_list::sort  = forward_list 멤버, Forward로 OK, 병합 정렬 (merge sort), stable

차이가 생긴 이유 3가지:
  ① iterator 카테고리 — list iterator는 RandomAccess 아님 → std::sort 컴파일 에러
  ② 알고리즘 적합성 — quicksort partition은 무작위 접근 필수, list엔 병합 정렬 (merge sort)가 자연
  ③ 비용 구조 — list::sort는 데이터 이동 0 (포인터만), 큰 객체일수록 이득 큼

같은 패턴 (멤버 vs 알고리즘):
  set/map::find       → O(log n)  ← 알고리즘 std::find는 O(n)
  unordered_map::find → O(1) 평균
  list::merge/splice/unique/reverse → 노드 재연결만

정렬 family:
  std::stable_sort    → vector·deque·array 용 안정 정렬, O(n) 메모리 또는 O(n log² n) 시간
  std::partial_sort   → 상위 k개만, O(n log k)
  std::nth_element    → k번째만 제자리, O(n) 평균

언리얼:
  Algo::Sort / TArray::Sort           — std::sort 대응
  Algo::StableSort / TArray::StableSort — std::stable_sort 대응
  TLinkedList — Sort 멤버 함수 없음 (1급 X, 수동 구현)

표준 요구:
  list::sort → stable + O(n log n) 보장
  std::sort  → 평균/최악 O(n log n) 보장 (introsort 덕분)

---

회귀 다리 — 다른 CS 파일 연결

파일	연결 지점
13_vector_vs_list	메모리 레이아웃·캐시 친화성. list가 정당화되는 시나리오(큰 객체 + splice + iterator 안정성)가 list::sort의 가치와 직결
16_stl_containers	STL 컨테이너 카테고리 정리. forward_list / list / vector iterator 카테고리 표
17_find_vs_binary_search	9-1 iterator 카테고리(Input → Forward → Bidirectional → RandomAccess), 멤버 vs 알고리즘 컨벤션. 이번 18번이 그 컨벤션의 정렬 버전
15_pushback_vs_emplaceback	move 생성자·객체 이동 비용. list::sort가 “데이터 이동 0”으로 회피하는 비용의 정체
14_std_map	RB-Tree 자료구조의 invariant 유지(set/map은 정렬 멤버가 불필요한 이유). list와의 대비