병합 정렬(Merge Sort)의 개념
병합 정렬은 '분할 정복(Divide and Conquer)' 전략을 기반으로 하는 효율적인 정렬 알고리즘입니다. 큰 문제를 작은 하위 문제로 쪼갠 뒤 각각을 해결하고, 다시 합쳐서 전체 문제를 해결하는 방식입니다. 이 알고리즘은 데이터의 상태와 무관하게 일정한 성능을 보장하는 것이 특징입니다.
정렬 프로세스
- 분할(Divide): 정렬되지 않은 리스트를 절반으로 나누어 두 개의 하위 리스트로 만듭니다.
- 정복(Conquer): 각 하위 리스트를 재귀적으로 병합 정렬을 이용해 정렬합니다. 리스트의 크기가 1이 되면 정렬된 것으로 간주합니다.
- 결합(Combine): 정렬된 하위 리스트들을 하나의 정렬된 리스트로 합칩니다. 이 과정에서 실질적인 정렬이 이루어집니다.
1. 배열 기반의 병합 정렬 구현
가장 일반적인 배열을 이용한 병합 정렬 구현 방식입니다. 추가적인 메모리 공간(버퍼)이 필요합니다.
public class MergeSortProvider {
public static void main(String[] args) {
int[] data = {25, 10, 36, 5, 92, 47, 11, 8};
int[] buffer = new int[data.length];
executeMergeSort(data, 0, data.length - 1, buffer);
for (int val : data) {
System.out.print(val + " ");
}
}
private static void executeMergeSort(int[] arr, int start, int end, int[] temp) {
if (start < end) {
int middle = start + (end - start) / 2;
// 왼쪽 그룹 정렬
executeMergeSort(arr, start, middle, temp);
// 오른쪽 그룹 정렬
executeMergeSort(arr, middle + 1, end, temp);
// 두 그룹 병합
mergeSections(arr, start, middle, end, temp);
}
}
private static void mergeSections(int[] arr, int start, int mid, int end, int[] temp) {
int leftPtr = start;
int rightPtr = mid + 1;
int currentIdx = 0;
// 작은 순서대로 임시 배열에 복사
while (leftPtr <= mid && rightPtr <= end) {
if (arr[leftPtr] <= arr[rightPtr]) {
temp[currentIdx++] = arr[leftPtr++];
} else {
temp[currentIdx++] = arr[rightPtr++];
}
}
// 남은 요소 처리
while (leftPtr <= mid) {
temp[currentIdx++] = arr[leftPtr++];
}
while (rightPtr <= end) {
temp[currentIdx++] = arr[rightPtr++];
}
// 원본 배열로 복사
for (int i = 0; i < currentIdx; i++) {
arr[start + i] = temp[i];
}
}
}
2. 공간 최적화를 고려한 병합 방식
병합 과정에서 원본 데이터를 임시 배열에 먼저 복사한 후, 원본 배열에 직접 정렬된 값을 채워 넣는 방식입니다.
private static void optimizedMerge(int[] target, int low, int mid, int high, int[] helper) {
// 임시 배열에 현재 범위 복사
for (int k = low; k <= high; k++) {
helper[k] = target[k];
}
int left = low;
int right = mid + 1;
for (int k = low; k <= high; k++) {
if (left > mid) {
target[k] = helper[right++];
} else if (right > high) {
target[k] = helper[left++];
} else if (helper[left] <= helper[right]) {
target[k] = helper[left++];
} else {
target[k] = helper[right++];
}
}
}
3. 단일 연결 리스트 정렬
연결 리스트(Linked List)는 인덱스를 통한 접근이 어렵기 때문에 'Fast & Slow Pointer' 기법을 사용하여 중간 지점을 찾고 분할합니다.
class ListSorter {
public ListNode sort(ListNode head) {
if (head == null || head.next == null) return head;
// 중간 노드 찾기
ListNode prev = null, slow = head, fast = head;
while (fast != null && fast.next != null) {
prev = slow;
slow = slow.next;
fast = fast.next.next;
}
// 리스트 절단
prev.next = null;
// 재귀적 정렬 및 병합
return merge(sort(head), sort(slow));
}
private ListNode merge(ListNode l1, ListNode l2) {
ListNode dummy = new ListNode(0);
ListNode tail = dummy;
while (l1 != null && l2 != null) {
if (l1.val < l2.val) {
tail.next = l1;
l1 = l1.next;
} else {
tail.next = l2;
l2 = l2.next;
}
tail = tail.next;
}
tail.next = (l1 != null) ? l1 : l2;
return dummy.next;
}
}
4. K개의 정렬된 리스트 병합 (K-way Merge)
여러 개의 정렬된 리스트를 하나로 합칠 때도 병합 정렬의 분할 정복 아이디어를 적용하여 효율적으로 처리할 수 있습니다.
class KListMerger {
public ListNode mergeKLists(ListNode[] lists) {
if (lists == null || lists.length == 0) return null;
return splitAndMerge(lists, 0, lists.length - 1);
}
private ListNode splitAndMerge(ListNode[] lists, int start, int end) {
if (start == end) return lists[start];
int mid = start + (end - start) / 2;
ListNode left = splitAndMerge(lists, start, mid);
ListNode right = splitAndMerge(lists, mid + 1, end);
return mergeTwo(left, right);
}
private ListNode mergeTwo(ListNode n1, ListNode n2) {
if (n1 == null) return n2;
if (n2 == null) return n1;
if (n1.val < n2.val) {
n1.next = mergeTwo(n1.next, n2);
return n1;
} else {
n2.next = mergeTwo(n1, n2.next);
return n2;
}
}
}
알고리즘 성능 요약
- 시간 복잡도: 평균 및 최악의 경우 모두
O(N log N)입니다. 데이터를 나눌 때log N단계가 발생하며, 각 단계에서N번의 비교가 이루어지기 때문입니다. - 공간 복잡도: 배열 기반 구현 시 추가적인 배열 공간이 필요하므로
O(N)입니다. - 안정성(Stability): 동일한 값의 상대적 순서가 유지되는 Stable Sort입니다.
- 특이사항: 순차적인 데이터 접근 방식을 사용하므로 연결 리스트 정렬에 매우 효율적이며, 데이터가 너무 커서 메모리에 다 담을 수 없는 외부 정렬(External Sort)의 기본 원리로 사용됩니다.