병합 정렬

 

 

정의

하나의 배열을 두개로 균등한 배열로 분할하고 분할된 배열을 각각 정렬한 다음, 이를 다시 합하여 정렬을 완성하는 알고리즘이다.
분할 정복의 일종으로, 하나의 큰 문제를 두 개의 작은 문제로 분할하여 해결한 다음, 결과를 모아서 문제를 완전히 해결하는 전략이다.

 

동작과정

1. 리스트의 길이가 1 이하이면 이미 정렬된 것으로 보고 그대로 데이터 리턴. 그렇지 않은 경우에는
2. 분할(divide) : 정렬되지 않은 리스트를 절반으로 잘라 비슷한 크기의 두 부분 리스트로 나눈다.
3. 정복(conquer) : 각 부분 리스트를 재귀적으로 합병 정렬을 이용해 정렬한다.
4. 결합(combine) : 두 부분 리스트를 다시 하나의 정렬된 리스트로 합병한다.

 

 

시간복잡도

• 최선의 경우 O(nlogn), 평균의 경우 O(nlogn), 최약의 경우도 O(nlogn)이다.
• 배열의 길이를 N = 2ⁿ이하라 했을 때, 합병은 n번이 일어난다. 한번의 합병 단계에서는 여러번의 합병이 일어나고, 임시배열에 원소를 정렬하는 과정에서 원소 개수만큼의 비교 연산이 수행된다. 또한, 임시배열의 원소를 원래의 배열로 이동시키는 과정에서 원소 개수만큼의 이동연산이 수행된다. 각각의 단계는 여러번의 합병을 포함하고 있으나, 결국 모든 원소들의 개수 합은 N개이므로 각각의 단계에서 2N만큼의 이동, 비교 연산이 일어난다. 결국 시간복잡도는 합병 단계 n번, 각각의 단계에서 연산 횟수 2N = O(nN)이 되고, N = 2ⁿ, n = logN이므로 합병 정렬 시간복잡도는 O(nN) = O(NlogN)이 된다.

 

공간복잡도

• 별도의 추가적 메모리가 즉 합병할 공간이 필요하기에 O(n)이다.

 

코드

• mergeSort

public void mergeSort(int[] array, int left, int right) {
    
    if(left < right) {
        int mid = (left + right) / 2;
        
        mergeSort(array, left, mid);
        mergeSort(array, mid+1, right);
        merge(array, left, mid, right);
    }

• merge()

public static void merge(int[] array, int left, int mid, int right) {
    int[] L = Arrays.copyOfRange(array, left, mid + 1);
    int[] R = Arrays.copyOfRange(array, mid + 1, right + 1);
    
    int i = 0, j = 0, k = left;
    int ll = L.length, rl = R.length;
    
    while(i < ll && j < rl) {
        if(L[i] <= R[j]) {
            array[k] = L[i++];
        }
        else {
            array[k] = R[j++];
        }
        k++;
    }
    
    // remain
    while(i < ll) {
        array[k++] = L[i++];
    }
    while(j < rl) {
        array[k++] = R[j++];
    }
}

이미 합병의 대상이 되는 두 영역이 각 영역에 대해서 정렬이 되어있기 때문에 단순히 두 배열을 순차적으로 비교하면서 정렬할 수가 있다.

합병정렬은 순차적인 비교로 정렬을 진행하므로, LinkedList의 정렬이 필요할 때 사용하면 효율적이다.

LinkedList는 삽입, 삭제 연산에서 유용하지만 접근 연산에서는 비효율적이다.

 

따라서 임의로 접근하는 퀵정렬을 활용하면 오버헤드 발생이 증가하게 된다.

배열은 인덱스를 이용해서 접근이 가능하지만, LinkedList는 Head부터 탐색해야 한다.
배열[O(1)] vs LinkedList[O(n)]

private void solve() {
    int[] array = { 230, 10, 60, 550, 40, 220, 20 };
 
    mergeSort(array, 0, array.length - 1);
 
    for (int v : array) {
        System.out.println(v);
    }
}
 
public static void mergeSort(int[] array, int left, int right) {
    if (left < right) {
        int mid = (left + right) / 2;
 
        mergeSort(array, left, mid);
        mergeSort(array, mid + 1, right);
        merge(array, left, mid, right);
    }
}
 
public static void merge(int[] array, int left, int mid, int right) {
    int[] L = Arrays.copyOfRange(array, left, mid + 1);
    int[] R = Arrays.copyOfRange(array, mid + 1, right + 1);
 
    int i = 0, j = 0, k = left;
    int ll = L.length, rl = R.length;
 
    while (i < ll && j < rl) {
        if (L[i] <= R[j]) {
            array[k] = L[i++];
        } else {
            array[k] = R[j++];
        }
        k++;
    }
 
    while (i < ll) {
        array[k++] = L[i++];
    }
 
    while (j < rl) {
        array[k++] = R[j++];
    }
}

 

퀵 정렬과의 차이점

퀵 정렬 : 피벗을 통해 정렬(partition) -> 영역을 나눔(quickSort)

합병정렬: 영역을 쪼갤 수 있을 만큼 쪼갬(mergeSort) -> 정렬(merge)

 

장점

• 성능이 좋다.
• 연결 리스트로 레코드 구성 시 유리한 면이 있다(제자리 정렬도 가능)

 

 

단점

• 별도의 임시 배열이 필요하다(제자리 정렬)이 아니다.
• 추가적인 메모리를 할당할 수 없을 때 퀵 정렬을 사용해야 하는 단점이 있다.

 

 

 

출처:

https://velog.io/@delmasong/Algorithm-Merge-Sort-%EB%B3%91%ED%95%A9-%EC%A0%95%EB%A0%AC

https://gyoogle.dev/blog/algorithm/Merge%20Sort.html