병합 정렬(Merge Sort) 알고리즘 상세 가이드: 배열과 연결 리스트 구현

병합 정렬(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)의 기본 원리로 사용됩니다.

태그: MergeSort DataStructure algorithm java SortingAlgorithm

11월 2일 13:42에 게시됨