[정렬] 병합 정렬 : Merge Sort

 

 

📌 병합 정렬 : Merge Sort

✅ 분할 정복(Divide and Conquer) 기법을 사용한 정렬 알고리즘

✅ 데이터를 여러 부분으로 나누고 각각을 정렬한 후 병합하여 전체를 정렬

✅ 시간 복잡도 : \(O(n \log n)\)

import java.util.Arrays;

public class MergeSort {
    public static void main(String[] args) {
        int[] arr = {1, 10, 5, 8, 7, 6, 4, 3, 2, 9};
        mergeSort(arr, 0, arr.length - 1);
        System.out.println("결과: " + Arrays.toString(arr));
    }

    public static void mergeSort(int[] arr, int start, int end){
        if(start < end){
            int mid = (start + end) / 2;
            mergeSort(arr, start, mid);
            mergeSort(arr, mid + 1, end);
            merge(arr, start, mid, end);
        }
    }

    public static void merge(int[] arr, int start, int mid, int end){
        int[] temp = new int[end - start + 1];
        int i = start;
        int j = mid + 1;
        int k = 0;
        
        //작은 순서대로 배열 삽입
        while(i <= mid && j <= end){
            if(arr[i] <= arr[j]){
                temp[k++] = arr[i++];
            }else{
                temp[k++] = arr[j++];
            }
            //temp[k++] = arr[i] <= arr[j] ? arr[i++] : arr[j++]; 로도 가능
        }
        
        //남은 데이터 삽입
        while(i <= mid){
            temp[k++] = arr[i++];
        }

        while(j <= end){
            temp[k++] = arr[j++];
        }
        
        //정렬된 배열 삽입
        for(i = start, k = 0; i <= end; i++, k++){
            arr[i] = temp[k];
        }
    }
}

 

 

---

 

 

1. 분할 (Divide)

• 주어진 배열을 반으로 나눈다.
• 이는 재귀적으로 수행되며, 배열을 더 이상 나눠질 수 없을 때까지 반복

 

2. 정복 (Conquer)

• 분할된 부분 배열을 정렬한다.
• 이 정렬은 재귀적으로 수행
• 더 이상 배열이 분할되지 않고 하나의 원소로 이뤄진 배열이 될 때까지 이 과정을 반복

 

3. 병합 (Merge)

• 정렬된 부분 배열들을 하나로 합친다.
• 두 개의 정렬된 부분 배열을 비교하면서, 두 배열을 오름차순으로 정렬된 하나의 배열로 합친다.