병합정렬

 

분할 정복(Divide and Conquer) 알고리즘의 한 종류
안정적이고 효율적인 정렬 방식
정렬 과정에서 배열을 점점 작게 나누고 다시 합치며 정렬된 상태로 병합

 

1. 분할(Divide)

• 배열을 절반으로 나눈다.
• 크기가 1 이하가 될 때까지 반복적으로 나눈다.

2. 정복(Conquer)

• 나눠진 배열을 정렬된 상태로 병합(Merge)한다.

3. 병합(Merge)

• 두 개의 정렬된 서브 배열을 하나의 정렬된 배열로 결합한다.

 

특징

• 시간 복잡도
  • 최악, 최선, 평균
    • O(n log n)
    • 분할에 O(log n), 병합에 O(n)이 걸리기 때문에 항상 O(n log n)
• 공간 복잡도
  • O(n)
  • 추가적인 병합 배열이 필요하므로, 입력 배열 크기만큼 추가 메모리가 필요
• 안정 정렬
  • 동일한 값의 순서가 유지

 

장점

• 안정 정렬
  • 동일한 값의 순서가 유지
• 일관된 시간 복잡도
  • 데이터 패턴에 상관없이 항상 O(n log n)

 

단점

• 공간 복잡도 높음
  • 추가 메모리가 필요
• 작은 배열에서는 비효율적
  • 분할과 병합의 오버헤드 때문에 데이터가 작을 경우 삽입 정렬이나 퀵 정렬이 더 빠르다.

 

JAVA

import java.util.Arrays;

public class MergeSort {
    public static void mergeSort(int[] arr, int[] temp, int leftStart, int rightEnd) {
        if (leftStart >= rightEnd) {
            return;
        }

        int mid = (leftStart + rightEnd) / 2;
        mergeSort(arr, temp, leftStart, mid);  // 왼쪽 분할
        mergeSort(arr, temp, mid + 1, rightEnd);  // 오른쪽 분할
        merge(arr, temp, leftStart, mid, rightEnd);  // 병합
    }

    private static void merge(int[] arr, int[] temp, int leftStart, int mid, int rightEnd) {
        int left = leftStart;
        int right = mid + 1;
        int index = leftStart;

        // 두 부분 병합
        while (left <= mid && right <= rightEnd) {
            if (arr[left] <= arr[right]) {
                temp[index] = arr[left];
                left++;
            } else {
                temp[index] = arr[right];
                right++;
            }
            index++;
        }

        // 남은 요소 처리
        System.arraycopy(arr, left, temp, index, mid - left + 1);
        System.arraycopy(arr, right, temp, index, rightEnd - right + 1);
        System.arraycopy(temp, leftStart, arr, leftStart, rightEnd - leftStart + 1);
    }

    public static void main(String[] args) {
        int[] array = {5, 3, 8, 6, 2};
        int[] temp = new int[array.length];
        System.out.println("정렬 전: " + Arrays.toString(array));
        mergeSort(array, temp, 0, array.length - 1);
        System.out.println("정렬 후: " + Arrays.toString(array));
    }
}

 

Python

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

    # 중간점 계산 및 분할
    mid = len(arr) // 2
    left = merge_sort(arr[:mid])
    right = merge_sort(arr[mid:])

    # 병합
    return merge(left, right)

def merge(left, right):
    result = []
    i = j = 0

    # 두 배열을 병합
    while i < len(left) and j < len(right):
        if left[i] <= right[j]:
            result.append(left[i])
            i += 1
        else:
            result.append(right[j])
            j += 1

    # 남은 요소 추가
    result.extend(left[i:])
    result.extend(right[j:])
    return result


array = [5, 3, 8, 6, 2]
print("정렬 전:", array)
sorted_array = merge_sort(array)
print("정렬 후:", sorted_array)

 

 

차이

• 퀵정렬
  • 우선 피벗을 통해 정렬(partition) → 영역을 쪼갬(quickSort)
• 합병정렬
  • 영역을 쪼갤 수 있을 만큼 쪼갬(mergeSort) → 정렬(merge)