합병정렬 알고리즘 :: 마이구미

이 글은 합병정렬(merge sort) 또는 머지소트 라고 불리는 정렬 알고리즘을 다룬다.

누구나 한번쯤 들어봤고, 구현해본 정렬 중 하나이다.

빠른 정렬에 분류되고 퀵정렬과 많이 언급되는 정렬이다.

이유는 분할 정복 방식을 따르기 때문이다.

퀵 정렬 - http://mygumi.tistory.com/308

1. 합병정렬이란 무엇인가?

2. 합병정렬은 어떻게 구현하는가?

3. 합병정렬의 유용한 예는 언제인가?

합병정렬은 분할 정복 방법을 통해 구현된다.

분할 정복이란, 큰 문제를 작은 문제 단위로 쪼개면서 해결해나가는 방식이다.

(* 이전 글에서 다룬 퀵정렬도 분할 정복 방식을 가진다.)

시간복잡도는 최악, 최선, 평균 모두 O(nlogn) 을 가진다.

또한 안정 정렬로 속한다. (안정 정렬의 의미를 모른다면 참고글)

재귀 방식으로 구현될 수 있어, 코드가 복잡하지 않다.

전체적인 흐름만 이해한다면, 쉽게 이해할 수 있다.

요소를 쪼갠 후, 다시 합병시키면서 정렬해나가는 방식이다.

쪼개는 방식은 퀵정렬과 같은 방식으로, 왼쪽 오른쪽을 분리시킨다.

우선 전체적인 흐름을 볼 수 있는 코드를  통해 퀵정렬과 합병정렬을 비교해본다.

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);
    }
}

public void quicksort(int[] array, int left, int right) {
    if (left >= right) {
        return;
    }
    int pi = partition();

    quicksort(array, left, pi - 1);
    quicksort(array, pi + 1, right);
}

정렬 로직에 있어, 퀵정렬은 partition(), 합병정렬은 merge() 메소드가 된다.

퀵정렬의 경우 우선 피벗을 통해 정렬을 우선적으로한 후(partition), 영역을 쪼갠다.(quicksort)

반대로 합병정렬은 영역을 쪼갤 수 있을 만큼 쪼갠 후(mergesort), 정렬한다.(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++];
    }
}

merge() 메소드에서 단순히 두 영역 배열로 만들어서 순차적으로 비교하면서 정렬하는 것을 볼 수 있다.

이것이 가능한 이유는 합병의 대상이 되는 두 영역은 각 영역에서 대해서는 이미 정렬되어있기 때문이다.

그래서 단순히 두 배열을 순차적으로 비교하여 정렬할 수 있게 된다.

합병정렬의 과정을 설명하면서 순차적이라는 말을 많이 사용했다.

그 이유는 합병정렬이 사용되는 예를 설명하기 위해서다.

합병정렬은 링크드리스트(LinkedList) 이 정렬이 필요로 할 때 유용하다.

극단적인 예로, LinkedList 의 요소를 정렬하기 위해 퀵정렬을 사용한다면 어떻게 될까?

결과적으로 성능이 좋지 않다.

왜냐하면 퀵정렬은 순차적 접근이 아닌 임의적으로 접근하기 때문이다.

자세히 설명하자면 LinkedList 는 삽입 및 삭제 연산에 있어, 유용하지만 접근 연산에 있어서는 유용하지않는다.

배열의 경우에는 인덱스를 통해 접근하기 때문에 시간복잡도가 O(1) 이지만, LinkedList 는 Head부터 탐색해야하기때문에 O(n) 이다.

그렇기에, 임의적인 접근에 있어서는 오버헤드가 증가한다.

이러한 이유로 LinkedList 는 순차적인 접근과 같은 합병정렬을 사용하는 것이 유용하다.

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++];
    }
}