[Algorithm] 병합 정렬 (Merge Sort)

병합 정렬

  병합 정렬은 먼저 입력을 반으로 나눈다. 이렇게 나눈 전반부와 후반부를 각각 독립적으로 정렬한다. 마지막으로 정렬된 두 부분을 합쳐서, 즉 병합하여 정렬된 배열을 얻는다. 여기서 전반부를 정렬할 때도 역시 반으로 나눈 다음 정렬해서 병합한다. 즉, 원래의 정렬 문제와 성격이 똑같고 단지 크기만 반으로 줄었을 뿐이다. 후반부에 대한 정렬도 마찬가지다. 병합 정렬은 자신에 비해 크기가 반인 문제를 두 개 푼 다음, 이들을 병합하는 일을 재귀적으로 반복한다. 

 

병합 정렬의 작동 과정 (출처:쉽게 배우는 알고리즘)

병합 정렬 구현

public class MergeSort {

    public static void main(String[] args) {
        int[] arrays = {6, 3, 1, 21};
        mergeSort(arrays, 0, arrays.length - 1);
    }

    private static void mergeSort(int[] arrays, int p, int r) {
        if (p < r) {
            int mid = (p + r) / 2;
            mergeSort(arrays, p, mid);
            mergeSort(arrays, mid + 1, r);
            merge(arrays, p, mid, r);
        }
    }

    private static void merge(int[] arrays, int p, int mid, int r) {
        int i = p;
        int j = mid + 1;
        int k = p;
        int[] temp = new int[arrays.length];
        while (i <= mid && j <= r) {
            if (arrays[i] < arrays[j]) {
                temp[k++] = arrays[i++];
            } else {
                temp[k++] = arrays[j++];
            }
        }
        while (i <= mid)
            temp[k++] = arrays[i++];
        while (j <= r)
            temp[k++] = arrays[j++];
        for (int index = p; index < k; index++) {
            arrays[index] = temp[index];
        }
    }
}