🔍병합 정렬 알고리즘이란?

병합정렬(Merge Sort)은 데이터를 나눠서 정렬하고 다시 합치는 과정을
반복하는 정렬 알고리즘입니다

📌병합 정렬의 동작 방식

병합정렬은 분할 정복(Divide and Conquer) 방식을 사용하며,
크게 두 가지 단계로 나눠집니다

1단계: 분할(Divide)

정렬할 배열을 더 이상 나눌 수 없을 때까지 반씩 계속 나눕니다
최종적으로 배열의 크기가 1이 되면 정렬된 것으로 간주합니다

2단계: 병합(Merge)

나눠진 배열들을 두 개씩 합쳐나갑니다
이때 각 배열의 맨 앞 원소들을 비교해 작은 순서대로 합칩니다

🎈 회차별 비교 예시

실제 예시를 통해 병합정렬의 동작 방식을 살펴보겠습니다
예를 들어, [7, 3, 5, 2, 8, 1, 4, 6] 배열을 오름차순으로 정렬할 것입니다

🎈 1회차 비교 과정:

• 배열을 두 그룹 [7, 3, 5, 2]와 [8, 1, 4, 6]으로 나눕니다

🎈 2회차 비교 과정:

• [7, 3, 5, 2]는 [7, 3]과 [5, 2]로, [8, 1, 4, 6]은 [8, 1]과 [4, 6]으로 나눕니다

🎈 3회차 비교 과정:

• 다시 개별 요소까지 나누어 [7], [3], [5], [2], [8], [1], [4], [6]이 됩니다

🎈 병합 1회차:

• [7]과 [3]을 비교하여 [3, 7]로 병합합니다
• [5]와 [2]를 비교하여 [2, 5]로 병합합니다
• [8]과 [1]을 비교하여 [1, 8]로 병합합니다
• [4]와 [6]을 비교하여 [4, 6]으로 병합합니다

🎈 병합 2회차:

• [3, 7]과 [2, 5]를 비교하여 [2, 3, 5, 7]로 병합합니다
• [1, 8]과 [4, 6]을 비교하여 [1, 4, 6, 8]로 병합합니다

🎈 최종 병합:

• [2, 3, 5, 7]과 [1, 4, 6, 8]을 비교하며 최종적으로 [1, 2, 3, 4, 5, 6, 7, 8]로 정렬됩니다

이제 모든 숫자가 오름차순으로 정렬되었습니다 [1, 2, 3, 4, 5, 6, 7, 8]

🚀 실제 코드로 구현하기

위에서 설명한 동작 방식을 코드로 구현하면 다음과 같습니다

public static void main(String[] args) throws IOException {   
    int[] arr = {7, 3,5,2,8,1,4,6};  
    divide(arr, 0, arr.length-1);  
  
    for (int i = 0; i < arr.length; i++) {  
        System.out.print(arr[i]+" ");  
    }
}  
  
private static void divide(int[] arr, int left, int right) {  
    if(left < right){  
        int mid = (left + right) / 2;  
        divide(arr, left, mid);  
        divide(arr, mid + 1, right);  
        merge(arr, left, mid, right);  
    }  
}  
  
private static void merge(int[] arr, int left, int mid, int right){  
    int[] tmp = new int[right - left + 1];  
    int i = left;  
    int j = mid + 1;  
    int k = 0;  
  
    while(i <= mid && j <= right){  
        if(arr[i] <= arr[j]){  
            tmp[k++] = arr[i++];  
        }else{  
            tmp[k++] = arr[j++];  
        }  
    }  
  
    while(i <= mid){  
        tmp[k++] = arr[i++];  
    }  
    while(j <= right){  
        tmp[k++] = arr[j++];  
    }  
  
    for (int l = 0; l < tmp.length; l++) {  
        arr[left + l] = tmp[l];  
    }  
}

이 코드를 실행하면 배열은  [1, 2, 3, 4, 5, 6, 7, 8]의 형태로 오름차순 정렬됩니다

🛠️ 시간복잡도

• 최악, 평균, 최선 모두: O(n log n)

3가지 경우 모두 같은 이유는 항상 배열을 반씩 나누고 다시 병합하면서
전체를 한 번씩 확인하기 때문입니다

장점

• 안정 정렬: 중복된 요소들의 원래 순서를 유지합니다
• 성능이 일관적: 최악의 경우에도 효율성이 유지됩니다
• 대규모 데이터 처리 가능: 병렬 처리에 유리한 구조입니다

단점

• 추가 메모리 필요: 병합 과정에서 임시 배열을 사용하므로 메모리 효율이 좋지 않습니다
• 소규모 데이터에는 비효율적: 작은 데이터셋은 더 간단한 알고리즘이 유리합니다

✍️ 결론

병합정렬은 데이터를 나눠서 정렬하고 다시 합치는 과정을 반복하는 정렬 알고리즘입니다

병렬 처리가 가능하므로 대규모 데이터를 처리하기 좋다는 장점이 있지만,
작은 데이터셋의 경우 오버헤드 때문에 상대적으로 비효율적이라는 단점이 있습니다