6. 새 노드 없이 합쳐도 호출 스택은 남는다
해설글
작성 · 4분 읽기 · 조회수 —수정
기초 개념과 예제를 보강하고 시리즈 흐름을 연결
더미 헤더가 필요하다고 적은 이유
합병 정렬은 입력을 절반으로 나누고, 각 절반을 재귀적으로 정렬한 뒤, 정렬된 두 결과를 합치는 분할 정복 알고리즘이다. 재귀 호출은 같은 함수를 더 작은 입력에 적용하고, 길이가 0이나 1이면 이미 정렬됐다고 보고 돌아온다.
이 글의 입력은 단일 연결 리스트다. 각 노드는 값과 다음 노드의 주소 next를 가진다. 배열처럼 a[mid]로 중간에 바로 갈 수 없고, next를 따라가야 한다.
head
↓
[4|next] → [1|next] → [3|next] → [2|NULL]
head는 첫 실제 노드를 가리키는 포인터다. 더미 헤더는 값으로 쓰지 않는 노드를 맨 앞에 하나 두어, 첫 노드를 붙이는 경우도 이후 노드를 붙이는 경우와 같은 코드로 처리하게 한다.
합병 정렬 실습 파일 첫 줄에는 강한 문장이 남아 있다.
단일연결리스트에서 헤더는 더미노드값을 갖고 있어야만 한다!!
노트에서도 “노드 포인터 하나만 선언하고 반환할 시엔 새로운 헤더가 없잖아요”라는 질문 뒤에 더미 헤더를 만들고 Header->next를 반환한다고 정리했다. 첫 노드를 붙일 때만 head를 따로 지정해야 하는 불편을 더미 하나가 없앤다. 모든 실제 노드는 언제나 tail->next에 붙이면 된다.
다만 동적으로 만든 더미 노드가 합병 정렬의 필수 조건은 아니다. 스택의 지역 변수로 둘 수도 있고, head와 tail을 별도로 관리할 수도 있다. 원문의 강조는 당시 선택한 구현을 이해한 기록으로 살리되 보편 법칙으로 넓히지는 않는다.
리스트를 절반으로 끊는 한 줄
배열은 중간 인덱스로 두 범위를 표현할 수 있지만 단일 연결 리스트에는 끝 인덱스가 없다. 느린 포인터와 빠른 포인터로 중간을 찾은 뒤 다음 연결을 실제로 끊는다.
Node *right = slow->next;
slow->next = NULL;
[4 → 1 → 3 → 2]에서 slow가 1을 가리킬 때 right에 3의 주소를 먼저 보관한다. 그다음 slow->next = NULL을 하면 왼쪽은 [4 → 1], 오른쪽은 [3 → 2]가 된다. 순서를 바꾸면 오른쪽 시작 주소를 잃는다. 이 둘을 재귀적으로 정렬하면 [1 → 4]와 [2 → 3]이 된다.
기존 노드를 다시 잇는 합병
두 정렬 리스트의 첫 노드를 비교해 작은 쪽을 결과의 tail 뒤에 붙인다.
| 단계 | 왼쪽 첫 값 | 오른쪽 첫 값 | 붙인 노드 | 결과 |
|---|---|---|---|---|
| 1 | 1 | 2 | 1 | 1 |
| 2 | 4 | 2 | 2 | 1 → 2 |
| 3 | 4 | 3 | 3 | 1 → 2 → 3 |
| 4 | 4 | 없음 | 남은 왼쪽 | 1 → 2 → 3 → 4 |
Node dummy = {0, 0, NULL};
Node *tail = &dummy;
if (left->key <= right->key) {
tail->next = left;
left = left->next;
} else {
tail->next = right;
right = right->next;
}
tail = tail->next;
여기서 새 데이터 노드는 없다. tail->next가 기존 노드를 가리키게 하고 입력 쪽 포인터를 다음 노드로 옮긴다. 더미는 지역 변수이므로 반환하는 것은 dummy.next, 즉 기존 노드 중 정렬 후 첫 노드다.
저장소에는 이 방식과 다른 구현도 있다. 5-1-1.c의 partition과 Merge는 newNode를 계속 호출해 값을 복사한다. 노트의 “기존 연결리스트 주소를 짜집기한다”는 설명은 기존 노드를 재연결하는 0930-1.c 쪽에 해당한다. 두 구현을 같은 공간 복잡도로 묶을 수 없다.
같은 값의 순서와 호출 스택
같은 키를 만났을 때 <=로 왼쪽 노드를 먼저 붙이면 원래 앞 절반의 노드가 먼저 남아 안정 정렬이 된다. [3a, 1, 3b, 2]를 정렬하면 [1, 2, 3a, 3b]가 되어야 한다. 비교를 <로 바꾸면 동률에서 오른쪽의 3b가 먼저 붙어 순서가 뒤집힐 수 있다.
이번 재현 코드는 빈 리스트, 한 노드, 홀수·짝수 길이, 중복 키와 원래 id 순서를 검사한다. 정렬 과정에서 새 노드를 만들지 않고 종료 시 입력 노드를 모두 해제한다. Sanitizer 실행에서 검사를 통과했다.
새 노드가 없다고 보조 공간이 완전히 O(1)은 아니다. 재귀 분할 깊이는 O(log n)이고 각 호출의 지역 포인터가 호출 스택에 남는다. 따라서 재귀 버전은 스택까지 세면 O(log n) 보조 공간이다. 0930-1.c 같은 bottom-up 반복 재연결 방식이면 이 호출 스택도 없앨 수 있다.
더미 헤더에 대한 질문에서 시작했지만 공간을 결정하는 것은 더미 하나가 아니었다. 분할할 때 연결을 어떻게 보존하는지, 병합에서 기존 노드를 잇는지 새로 복사하는지, 재귀를 쓰는지를 따로 보아야 한다.
참고한 기록과 코드
- 개인 노트 「5주차 - Merge Sort, Quick Sort」, 2025-10-20
Week5 Merge, Quick Sort/5-1-1.cWeek5 Merge, Quick Sort/0930-1.c