[Sort] 합병 정렬(Merge Sort)

합병 정렬(Merge Sort)

 

 

[출처: 위키]

정의: 여러 개의 정렬된 자료의 집합을 결합하여 한 개의 정렬된 집합으로 만드는 방법

Divide & Conquer !!!!

---

1단계

 

자 위와 같이 숫자를 두고 정렬을 해봅시다!!

합병 정렬의 개념은 일단 다시 그림을 그려서 설명해야 겠네요~

 

이렇게 처음에는 붙어있다고 생각하세요!!

여기서 1개의 원소집합을 갖는 부분 집합으로 쪼갭니다~

처음엔 요렇게 2등분 했다고 보죠

 

다음은 분리된 걸 또 분리.

 

또! 분리...

 

각각 1개의 원소로 분리 됬네요~?

네 여기까지 분할 단계를 끝마치네요~!

---

---

2단계

이젠 다시 합쳐야 할 시간입니다!!!

합치면서 정렬됩니다!!

자 위 그림에서 등분된 집합이 다시 합쳐지는 꼴을 봅시다!!

 

이렇게 4개의 부분 집합으로 다시 합쳐졌죠???

근데 합치면서 달라지신게 보일겁니다!!!

각 부분 집합이 정렬이 되었죠??

네. 여기가 포인트 입니다!

합쳐지면서 정렬이 이루어 집니다!

그럼 또 합쳐 봅시다!

 

자 이렇게 되었네요!!

마지막 단계만 남겨둔 상태군요...

 

이렇게 정렬이 완성이군요!!

여기서는 2-way 병합 정렬을 수행했습니다!!

2개의 정렬된 자료의 집합을 결합하여 하나의 집합으로 만드는 방식이거든요!!!

이처럼 n-way로 작성을 따로 할 수도 있습니다!!!

---

 

이 병합 정렬의 시간 복잡도(Time Complexity)는 아래와 같습니다!

모든 케이스에 대해

 

 

를 갖습니다!!!

자 그럼 소스 코드로 예제를 살펴 봅시다~

MergeMain.java

 

package Merge;
 
public class MergeMain {
    public static void main(String[] args) {
        int[] arr = { 69, 10, 30, 2, 16, 8, 31, 22 };
        MergeSort.mergeSort(arr, 0, arr.length - 1);
    }
}
 
 

MergeSort.java

 

 
package Merge;
 
import Selection.SelectionSort;
 
public class MergeSort {
    public static int[] sorted = new int[30];
 
    public static void mergeSort(int[] arr, int m, int n) {
        int middle;
        if (m < n) {
            middle = (m + n) / 2;
            mergeSort(arr, m, middle);
            mergeSort(arr, middle + 1, n);
            merge(arr, m, middle, n);
        }
    }
 
    public static void merge(int[] arr, int m, int middle, int n) {
        int i, j, k, t;
 
        i = m;
        j = middle + 1;
        k = m;
 
        while (i <= middle && j <= n) {
            if (arr[i] <= arr[j])
                sorted[k] = arr[i++];
            else
                sorted[k] = arr[j++];
            k++;
        }
 
        if (i > middle) {
            for (t = j; t <= n; t++, k++)
                sorted[k] = arr[t];
        } else {
            for (t = i; t <= middle; t++, k++)
                sorted[k] = arr[t];
        }
 
        for (t = m; t <= n; t++)
            arr[t] = sorted[t];
 
        System.out.println("\n 합병 정렬 >> ");
        SelectionSort.printArr(arr);
 
    }
}
 

결과는 아래와 같습니다!!