병합 정렬(Merge Sort)은 분할 정복(Divide and Conquer) 기법에 기반한 대표적인 정렬 알고리즘입니다. 전체 데이터 집합을 더 작은 단위로 나눈 뒤, 각 부분을 정렬된 순서에 맞게 다시 합쳐 하나의 완전한 정렬 집합으로 만듭니다. 최악의 경우에도 낮은 시간 복잡도를 보장하기 때문에 어떤 입력 상황에서든 안정적인 성능을 발휘한다는 점이 큰 장점입니다.
특히 연결 리스트는 병합 정렬을 통해 매우 효율적으로 정렬할 수 있습니다. 배열과 달리 연결 리스트에서 병합 작업은 새로운 메모리를 할당할 필요 없이 노드 간 링크(포인터)만 업데이트하면 되므로 구현이 간단하고 성능도 뛰어납니다. 이번 글에서는 이러한 접근 방식을 활용해 연결 리스트를 정렬하는 방법을 자세히 살펴보겠습니다.
병합 정렬 기법의 복잡도
시간 복잡도 − 모든 경우(최선·평균·최악)에 대해 O(n log n)
공간 복잡도 − O(n)
입력 − 정렬되지 않은 리스트: 14 20 78 98 20 45
출력 − 정렬 후 배열: 14 20 20 45 78 98
알고리즘
1. mergeList(ll1, ll2)
입력 − 병합할 두 개의 연결 리스트 ll1과 ll2
출력 − 병합된 하나의 연결 리스트
두 리스트의 헤드 값을 비교하여 더 작은 쪽을 새로운 헤드로 지정하고, 나머지 부분을 재귀적으로 병합하는 방식으로 동작합니다.
Begin
if ll1 is empty, then
return ll2
if ll2 is empty, then
return ll1
if data(ll1) <= data(ll2), then
new_head = ll1;
next(new_head) = mergeList(next(ll1), ll2)
else
new_head = ll2;
next(new_head) = mergeList(ll1, next(ll2))
return new_head
End
2. split_list(start, ll1, ll2)
입력 − 연결 리스트의 시작 포인터, 그리고 두 개의 출력 인자 ll1과 ll2
출력 − 원래 리스트에서 분할된 두 개의 연결 리스트
느린 포인터(slow)와 빠른 포인터(fast)를 활용하는 플로이드(Floyd)의 거북이-토끼 알고리즘과 유사한 방식으로, 리스트의 중간 지점을 찾아 두 부분으로 나눕니다.
Begin
slow := start
fast := next(start)
while fast is not null, do
fast := next(fast)
if fast is not null, then
slow := next(slow)
fast := next(fast)
end while
ll1 := start
ll2 := next(slow)
next(slow) := null
End
3. mergeSort(start)
입력 − 정렬할 연결 리스트
출력 − 정렬된 연결 리스트
리스트가 비어 있거나 노드가 하나뿐이라면 그대로 반환하고(기저 조건), 그렇지 않으면 분할 → 재귀적 정렬 → 병합의 순서로 진행합니다.
Begin
head = start
if head is null or next(head) is null, then
return
split_list(head, ll1, ll2)
mergeSort(ll1)
mergeSort(ll2)
start := mergeList(ll1, ll2)
End
C++ 전체 소스 코드
#include<bits/stdc++.h>
using namespace std;
class node { // 데이터와 다음 노드의 주소를 저장하는 노드 정의
public:
int data;
node *next;
};
void display(class node* start) {
node* p = start; // 현재 노드를 head로 설정
while(p != NULL) { // 현재 노드가 NULL이 아니면 계속 순회
cout << p -> data << " ";
p = p -> next; // 다음 노드로 이동
}
}
node* getNode(int d) {
node* temp = new node;
temp -> data = d;
temp -> next = NULL;
return temp;
}
node* mergeList(node* ll1, node* ll2) { // 두 개의 정렬된 리스트를 병합하는 함수
node* newhead = NULL;
if(ll1 == NULL)
return ll2;
if(ll2 == NULL)
return ll1;
// 리스트를 재귀적으로 병합
if(ll1 -> data <= ll2 -> data) {
newhead = ll1;
newhead -> next = mergeList(ll1->next,ll2);
} else {
newhead = ll2;
newhead -> next = mergeList(ll1,ll2->next);
}
return newhead;
}
void splitList(node* start, node** ll1,node** ll2) {
// Floyd의 거북이-토끼 알고리즘과 유사한 방식
node* slow = start;
node* fast = start -> next;
while(fast!= NULL) {
fast = fast -> next;
if(fast!= NULL) {
slow = slow -> next;
fast = fast -> next;
}
}
*ll1 = start;
*ll2 = slow -> next;
// 리스트 분할
slow -> next = NULL;
}
void mergeSort(node** start) {
node* head = *start;
node* ll1,*ll2;
// 기저 조건(base case)
if(head == NULL || head->next == NULL) {
return;
}
splitList(head,&ll1,&ll2); // 리스트를 반씩 분할
// 좌측과 우측 하위 리스트를 각각 정렬
mergeSort(&ll1);
mergeSort(&ll2);
// 두 개의 정렬된 리스트를 병합
*start = mergeList(ll1,ll2);
return;
}
int main() {
cout << "Creating the linked list: " << endl;
cout << "Enter 0 to stop building the list, else enter any integer" << endl;
int k,count = 1,x;
node* curr,*temp;
cin >> k;
node* head = getNode(k); // 리스트 생성, 첫 번째 노드
cin >> k;
temp = head;
while(k) {
curr = getNode(k);
temp -> next = curr; // 각 노드를 순차적으로 연결
temp = temp -> next;
cin >> k;
}
cout<<"Before sorting: " << endl;
display(head); // 리스트 출력
cout<<"\nAfter sorting: " << endl;
mergeSort(&head);
display(head);
return 0;
}
실행 결과
Creating the linked list:
Enter 0 to stop building the list, else enter any integer
89
54
15
64
74
98
10
24
26
0
Before sorting:
89 54 15 64 74 98 10 24 26
After sorting:
10 15 24 26 54 64 74 89 98
위 실행 결과에서 볼 수 있듯이, 사용자가 입력한 임의의 정수들로 구성된 연결 리스트가 병합 정렬을 통해 오름차순으로 올바르게 정렬됩니다. 이 알고리즘은 재귀 호출로 리스트를 계속 반으로 나눈 뒤 병합하는 구조이므로, 데이터가 이미 어느 정도 정렬되어 있거나 역순으로 배치된 최악의 경우에도 O(n log n)의 안정적인 성능을 유지한다는 점이 핵심 강점입니다.