병합 정렬 (Merge Sort) - JAVA

병합 정렬은 분할 정복 방식을 사용해 데이터를 분할하고 분할한 집합을 정렬하며 합치는 알고리즘 입니다.

시간 복잡도는 O(nlogn)입니다.

 

정렬 과정

출처 : https://ko.wikipedia.org/wiki/%ED%95%A9%EB%B3%91_%EC%A0%95%EB%A0%AC

최초에 N개의 그룹으로 나눕니다. 그림을 예로 들면 8개로 나누게 되고 이 상태에서 2개씩 그룹을 합치며 오름차순 정렬합니다.

(1), (2), (3), (4), (5), (6), (7), (8)

↓

(5, 6), (1, 3), (7, 8), (2, 4)

↓

(1, 3, 5, 6), (2, 4 ,7, 8)

↓

(1, 2, 3, 4, 5, 6, 7, 8)

 

 

소스 코드

public void mergeSort(int A[], int low, int high, int B[]){
    // 1. base condition
    if(low >= high) return;

    // 2. divide
    int mid = (low + high) / 2;

    // 3. conquer
    mergeSort(A, low, mid, B);
    mergeSort(A, mid+1, high, B);

    // 4. combine
    int i = low, j = mid+1;
    for(k = low;k <= high;++k){
        if(j > high ) B[k] = A[i++];
        else if(i > mid) B[k] = A[j++];
        else if(A[i] <= A[j]) B[k] = A[i++];
        else B[k] = A[j++];
    }

    // 5. copy
    for(i=low;i<=high;++i) A[i] = B[i];
}