병합 정렬

병합 정렬 (Merge Sort)

분할 정복(Divide and Conquer) 알고리즘을 기반으로 하는 정렬 방식으로, 리스트를 절반씩 나누어 정렬한 후 다시 합치면서 전체를 정렬하는 방법

핵심 요소

•

분할(Divide): 입력 배열을 같은 크기의 2개의 부분 배열로 분할

•

정복(Conquer): 부분 배열을 정렬

•

결합(Combine): 정렬된 부분 배열들을 하나의 배열로 병합

시간 복잡도

최선의 경우	O(n log n)
평균의 경우	O(n log n)
최악의 경우	O(n log n)
공간 복잡도	O(n)

주요 특징

•

안정 정렬(Stable Sort): 동일한 값에 대해 원래의 순서가 유지됨

•

비제자리 정렬(Not-in-place Sort): 추가적인 메모리 공간이 필요

•

분할 정복 방식: 문제를 작은 2개의 문제로 분리하고 해결한 후, 결과를 모아서 원래의 문제를 해결

예시 코드

public class MergeSort {
    public static void mergeSort(int[] arr, int left, int right) {
        if (left < right) {
            int mid = (left + right) / 2;
            mergeSort(arr, left, mid);
            mergeSort(arr, mid + 1, right);
            merge(arr, left, mid, right);
        }
    }
    
    private static void merge(int[] arr, int left, int mid, int right) {
        int n1 = mid - left + 1;
        int n2 = right - mid;
        
        int[] L = new int[n1];
        int[] R = new int[n2];
        
        for (int i = 0; i < n1; i++)
            L[i] = arr[left + i];
        for (int j = 0; j < n2; j++)
            R[j] = arr[mid + 1 + j];
            
        int i = 0, j = 0, k = left;
        
        while (i < n1 && j < n2) {
            if (L[i] <= R[j]) {
                arr[k] = L[i];
                i++;
            } else {
                arr[k] = R[j];
                j++;
            }
            k++;
        }
        
        while (i < n1) {
            arr[k] = L[i];
            i++;
            k++;
        }
        
        while (j < n2) {
            arr[k] = R[j];
            j++;
            k++;
        }
    }
    
    public static void main(String[] args) {
		    int[] arr = {64, 34, 25, 12, 22, 11, 90};
		    mergeSort(arr);
		    System.out.println(Arrays.toString(arr));
		}

}
Java
복사

자바 컬렉션으로 구현

import java.util.Arrays;
import java.util.List;
import java.util.ArrayList;

public class MergeSortCollection {
    public static void main(String[] args) {
        List<Integer> list = new ArrayList<>(Arrays.asList(64, 34, 25, 12, 22, 11, 90));
        
        // Collections.sort() 내부적으로 병합 정렬 사용
        Collections.sort(list);
        System.out.println("정렬된 리스트: " + list);
        
        // Arrays.sort()도 병합 정렬 기반
        Integer[] array = list.toArray(new Integer[0]);
        Arrays.sort(array);
        System.out.println("정렬된 배열: " + Arrays.toString(array));
    }
}
Java
복사

합병 정렬(Merge Sort) 정의

합병 정렬(Merge Sort)은 분할 정복 알고리즘의 일종으로, 주어진 배열을 반으로 나누어 각각을 재귀적으로 정렬한 후, 정렬된 두 배열을 병합(merge)하는 방식으로 동작합니다. 이 알고리즘은 안정 정렬에 속하며, 시간 복잡도가 O(n log n)으로 효율적인 정렬 방법입니다.

합병 정렬의 동작 과정은 크게 두 단계로 나눌 수 있습니다:

분할: 배열을 중간에서 계속 나누어가며 각 부분 배열을 만든다.

병합: 각 부분 배열을 정렬하여 하나의 정렬된 배열로 병합한다.

합병 정렬 순서도

배열 분할:

•

주어진 배열을 계속해서 반으로 나눈다. 각 부분 배열이 크기가 1이 될 때까지 분할을 계속한다.

배열 병합:

•

두 개의 정렬된 배열을 합쳐서 하나의 정렬된 배열로 만든다.

합병 정렬의 순서도

graph TD
    A["시작 [배열]"]
    B["배열을 두 부분으로 분할"]
    C1["왼쪽 부분 배열"]
    C2["오른쪽 부분 배열"]
    D1["왼쪽 배열 정렬"]
    D2["오른쪽 배열 정렬"]
    E["정렬된 두 배열 병합"]
    F["정렬 완료"]

    A --> B
    B --> C1
    B --> C2
    C1 --> D1
    C2 --> D2
    D1 --> E
    D2 --> E
    E --> F

    %% 설명 추가
    style A fill:#f9f,stroke:#333
    style F fill:#9ff,stroke:#333
    style E fill:#ff9,stroke:#333
Mermaid
복사

위 순서도는 병합 정렬의 기본적인 흐름을 보여줍니다. 배열을 분할하고, 각 부분을 정렬한 후, 다시 병합하는 과정을 나타냅니다.

이 순서도는 배열을 재귀적으로 분할하고 병합하여 정렬하는 과정을 시각적으로 나타낸 것입니다.

재귀호출 실행 순서

mergeSort(arr, 0, 7)
 ├─ mergeSort(arr, 0, 3)
 │   ├─ mergeSort(arr, 0, 1)
 │   │   ├─ mergeSort(arr, 0, 0)  → (기저 조건 충족, 리턴)
 │   │   ├─ mergeSort(arr, 1, 1)  → (기저 조건 충족, 리턴)
 │   │   ├─ merge(arr, 0, 0, 1)   → 두 개의 정렬된 배열 병합
 │   │
 │   ├─ mergeSort(arr, 2, 3)
 │   │   ├─ mergeSort(arr, 2, 2)  → (기저 조건 충족, 리턴)
 │   │   ├─ mergeSort(arr, 3, 3)  → (기저 조건 충족, 리턴)
 │   │   ├─ merge(arr, 2, 2, 3)   → 두 개의 정렬된 배열 병합
 │   │
 │   ├─ merge(arr, 0, 1, 3)       → 두 개의 정렬된 배열 병합
 │
 ├─ mergeSort(arr, 4, 7)
 │   ├─ mergeSort(arr, 4, 5)
 │   │   ├─ mergeSort(arr, 4, 4)  → (기저 조건 충족, 리턴)
 │   │   ├─ mergeSort(arr, 5, 5)  → (기저 조건 충족, 리턴)
 │   │   ├─ merge(arr, 4, 4, 5)   → 두 개의 정렬된 배열 병합
 │   │
 │   ├─ mergeSort(arr, 6, 7)
 │   │   ├─ mergeSort(arr, 6, 6)  → (기저 조건 충족, 리턴)
 │   │   ├─ mergeSort(arr, 7, 7)  → (기저 조건 충족, 리턴)
 │   │   ├─ merge(arr, 6, 6, 7)   → 두 개의 정렬된 배열 병합
 │   │
 │   ├─ merge(arr, 4, 5, 7)       → 두 개의 정렬된 배열 병합
 │
 ├─ merge(arr, 0, 3, 7)           → 최종적으로 모든 부분을 병합
Java
복사

실행 순서대로 분할 및 병합 과정 (Merge Sort 과정 시뮬레이션)

병합 정렬은 "분할 (Divide)" 후 "병합 (Merge)" 과정이 진행됩니다.

아래 표에서는 분할과 병합을 동시에 실행 순서대로 정리했습니다.

1. 초기 배열

{45, 12, 89, 33, 76, 27, 8, 19}
Plain Text
복사

2. 분할 & 병합 과정

단계	분할 (Divide)	병합 (Merge)
①	{45, 12, 89, 33} {76, 27, 8, 19}
②	{45, 12} {89, 33} {76, 27} {8, 19}
③	{45} {12} {89} {33} {76} {27} {8} {19}
④		{12, 45} {33, 89} {27, 76} {8, 19}
⑤		{12, 33, 45, 89} {8, 19, 27, 76}
⑥		{8, 12, 19, 27, 33, 45, 76, 89} (최종 정렬 완료)

3. 과정 상세 시각화

초기 상태: {45, 12, 89, 33, 76, 27, 8, 19}

1. 분할:  {45, 12, 89, 33}  |  {76, 27, 8, 19}
2. 분할:  {45, 12}  |  {89, 33}  |  {76, 27}  |  {8, 19}
3. 분할:  {45}  {12}  |  {89}  {33}  |  {76}  {27}  |  {8}  {19}
----------------------------------------------------
4. 병합:  {12, 45}  |  {33, 89}  |  {27, 76}  |  {8, 19}
5. 병합:  {12, 33, 45, 89}  |  {8, 19, 27, 76}
6. 병합:  {8, 12, 19, 27, 33, 45, 76, 89}  (최종 정렬 완료)
Plain Text
복사

4. 최종 결과

{8, 12, 19, 27, 33, 45, 76, 89}
Plain Text
복사

이처럼 병합 정렬은 분할(Divide) → 정렬 및 병합(Merge) 단계를 반복하며 정렬이 이루어집니다.