[알고리즘] 병합 정렬 (Merge Sort) - JAVA / 자바

병합 정렬(Merge Sort)

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

 - 부분 집합으로 분할(divide)하고, 각 부분 집합에 대해 정렬 작업을 완성(conquer)한 수에 정렬된 부분 집합들을 다시 결합(combine)하는 분할 정복(Divide And Conquer)기법 사용

 

 - 종류

    ㄴ 2-way 병합: 2개의 정렬된 자료의 집합을 결합하여 하나의 집합으로 만드는 병합 방법

⑴ 분할(divide) : 입력 자료를 같은 크기의 부분집합 2개로 분할
⑵ 정복(conquer) : 부분집합의 원소들을 정렬
                        : 부분집합의 크기가 충분히 작지 않으면 순환 호출을 이용하여 다시 분할 정복 기법 적용
⑶ 결합(combine) : 정렬된 부분집합들을 하나의 집합으로 통합

    ㄴ n-way 병합: n개의 정렬된 자료의 집합을 결합하여 하나의 집합으로 만드는 병합 방법

---

 - 수행 과정

정렬되지 않은 배열 L = {69, 10, 30, 2, 16, 8, 61, 22}

69

10

2

31

① 분할 단계 : 정렬할 전체 자료의 집합에 대해서 최소 원소의 부분집합이 될 때까지 분할 작업을 반복하여 1개의 원소를 가진 부분집합 4개를 만든다.

② 병합 단계 : 2개의 부분집합을 정렬하면서 하나의 집합으로 병합한다. 4개의 부분집합이 1개로 병합될 때까지 반복한다.

---

 - 알고리즘

mergeSort(list[], m, n)
    if (list[m:n]의 원소수 > 1) then {
        전체 집합을 두개의 부분집합으로 분할;
        mergeSort(list[], m, middle);
        mergeSort(list[], middle+1, n);
        merge(list[m:middle], a[middle+1:n]);
    }
end mergeSort()

 - 메모리 사용 공간 : 각 단계에서 새로 병합하여 만든 부분집합을 저장할 공간이 추가로 필요

                         : 원소 n개에 대해서 (2 x n) 개의 메모리 공간 사용

 - 연산 시간

    ㄴ 분할 단계 : n개의 원소를 분할하기 위해서 log 2n번의 단계 수행

    ㄴ 병합 단계 : 부분집합의 원소를 비교하면서 병합하는 단계에서 최대 n 번의 비교 연산 수행

 - 전체 병합 정렬의 시간 복잡도 : O(n log2 n)

---

< 분류 >

정렬 장소 - 내부 정렬(Internal Sort) > 병합 방식

[자료구조] 정렬 (Sort)