정렬 알고리즘 (Sorting Algorithms) - 삼분 병합 정렬 (3-Way Merge Sort)

3-Way Merge Sort (삼분 병합 정렬)

3-Way Merge Sort은 병합 정렬(Merge Sort)의 변형으로, 배열을 세 개의 하위 배열로 분할하여 각각을 재귀적으로 정렬한 후 병합하는 정렬 알고리즘입니다.
이는 기본 병합 정렬에서 두 개의 하위 배열로 나누는 대신, 세 개로 나누어 처리 속도를 개선하려는 시도입니다.

---

1. 작동 원리

1. 분할 (Divide):
   • 주어진 배열을 세 개의 하위 배열로 나눕니다.
   • 각각의 크기는 최대한 균등하게 나뉩니다.
2. 정복 (Conquer):
   • 세 개의 하위 배열을 재귀적으로 3-Way Merge Sort를 적용해 정렬합니다.
3. 병합 (Merge):
   • 세 개의 정렬된 배열을 병합하여 하나의 정렬된 배열로 만듭니다.

---

2. 알고리즘 특징

• 시간 복잡도:
  • 평균 및 최악의 경우 O(n log⁡3 n).
  • 이는 병합 정렬(O(n log⁡2 n)보다 약간 더 나은 성능을 제공할 수 있습니다.
• 공간 복잡도:
  • O(n)의 추가 공간이 필요합니다(병합 단계에서).
• 안정성:
  • 병합 정렬과 마찬가지로 안정 정렬입니다.
• 재귀 깊이 감소:
  • 병합 정렬에 비해 재귀 깊이가 줄어듭니다.

---

3. 3-Way Merge Sort 과정

예시: 배열 [9, 7, 5, 3, 1, 8, 6, 4, 2]

1. 분할:
   • 배열을 세 부분으로 나눕니다:
     • Left: [9, 7, 5]
     • Middle: [3, 1, 8]
     • Right: [6, 4, 2]
2. 재귀적으로 정렬:
   • Left → [5, 7, 9]
   • Middle → [1, 3, 8]
   • Right → [2, 4, 6]
3. 병합:
   • 세 정렬된 배열을 병합하여 최종 결과를 얻습니다:
     • [1, 2, 3, 4, 5, 6, 7, 8, 9]

---

4. 장점과 단점

장점:

• 효율성: 하위 배열의 개수를 늘려 재귀 깊이를 줄임으로써 실행 속도를 향상시킬 수 있습니다.
• 안정성: 동일한 값을 가진 데이터의 상대적 순서를 유지합니다.

단점:

• 추가 메모리 사용: 병합 단계에서 추가 공간이 필요합니다.
• 병합 복잡성 증가: 두 개의 배열을 병합하는 것보다 세 개를 병합하는 것이 더 복잡합니다.

---

5. Java 구현

import java.util.Arrays;

public class ThreeWayMergeSort {
    // Main function to perform 3-way merge sort
    public static void threeWayMergeSort(int[] arr) {
        if (arr.length <= 1) {
            return;
        }

        // Step 1: Divide the array into three parts
        int third = arr.length / 3;
        int[] left = Arrays.copyOfRange(arr, 0, third);
        int[] middle = Arrays.copyOfRange(arr, third, 2 * third);
        int[] right = Arrays.copyOfRange(arr, 2 * third, arr.length);

        // Step 2: Recursively sort each part
        threeWayMergeSort(left);
        threeWayMergeSort(middle);
        threeWayMergeSort(right);

        // Step 3: Merge the three sorted parts
        merge(arr, left, middle, right);
    }

    // Helper function to merge three sorted arrays
    private static void merge(int[] arr, int[] left, int[] middle, int[] right) {
        int i = 0, j = 0, k = 0, l = 0;

        while (i < left.length && j < middle.length && k < right.length) {
            if (left[i] <= middle[j] && left[i] <= right[k]) {
                arr[l++] = left[i++];
            } else if (middle[j] <= left[i] && middle[j] <= right[k]) {
                arr[l++] = middle[j++];
            } else {
                arr[l++] = right[k++];
            }
        }

        while (i < left.length && j < middle.length) {
            arr[l++] = (left[i] <= middle[j]) ? left[i++] : middle[j++];
        }
        while (j < middle.length && k < right.length) {
            arr[l++] = (middle[j] <= right[k]) ? middle[j++] : right[k++];
        }
        while (i < left.length && k < right.length) {
            arr[l++] = (left[i] <= right[k]) ? left[i++] : right[k++];
        }

        while (i < left.length) {
            arr[l++] = left[i++];
        }
        while (j < middle.length) {
            arr[l++] = middle[j++];
        }
        while (k < right.length) {
            arr[l++] = right[k++];
        }
    }

    // Main driver
    public static void main(String[] args) {
        int[] arr = {9, 7, 5, 3, 1, 8, 6, 4, 2};
        System.out.println("Original Array: " + Arrays.toString(arr));

        threeWayMergeSort(arr);

        System.out.println("Sorted Array: " + Arrays.toString(arr));
    }
}

---

6. Python 구현

def three_way_merge_sort(arr):
    if len(arr) <= 1:
        return arr

    # Step 1: Divide the array into three parts
    third = len(arr) // 3
    left = arr[:third]
    middle = arr[third:2*third]
    right = arr[2*third:]

    # Step 2: Recursively sort each part
    left = three_way_merge_sort(left)
    middle = three_way_merge_sort(middle)
    right = three_way_merge_sort(right)

    # Step 3: Merge the three sorted parts
    return merge(left, middle, right)

# Helper function to merge three sorted arrays
def merge(left, middle, right):
    result = []
    i = j = k = 0

    while i < len(left) and j < len(middle) and k < len(right):
        if left[i] <= middle[j] and left[i] <= right[k]:
            result.append(left[i])
            i += 1
        elif middle[j] <= left[i] and middle[j] <= right[k]:
            result.append(middle[j])
            j += 1
        else:
            result.append(right[k])
            k += 1

    while i < len(left) and j < len(middle):
        result.append(left[i] if left[i] <= middle[j] else middle[j])
        i += (left[i] <= middle[j])
        j += (left[i] > middle[j])

    while j < len(middle) and k < len(right):
        result.append(middle[j] if middle[j] <= right[k] else right[k])
        j += (middle[j] <= right[k])
        k += (middle[j] > right[k])

    while i < len(left) and k < len(right):
        result.append(left[i] if left[i] <= right[k] else right[k])
        i += (left[i] <= right[k])
        k += (left[i] > right[k])

    result.extend(left[i:])
    result.extend(middle[j:])
    result.extend(right[k:])

    return result

# Example usage
if __name__ == "__main__":
    arr = [9, 7, 5, 3, 1, 8, 6, 4, 2]
    print("Original Array:", arr)

    sorted_arr = three_way_merge_sort(arr)

    print("Sorted Array:", sorted_arr)

---

7. 활용 및 고려사항

활용:

• 재귀 깊이 제한: 재귀 호출 스택 크기를 줄이기 위해 사용됩니다.
• 특수 목적 정렬: 병합 정렬의 효율성을 높이고자 할 때 사용.

고려사항:

• O(n log⁡3 n)의 시간 복잡도는 병합 정렬보다 약간 개선되지만, 대부분의 실용적인 경우 이점이 미미할 수 있습니다.
• 병합 로직이 병합 정렬보다 복잡합니다.

3-Way Merge Sort는 이론적 흥미를 위한 알고리즘으로, 실무에서는 일반 병합 정렬보다 자주 사용되지 않습니다.